Network Science Quiz

Genetic Algorithms - TP Genetic Algorithms

• The MUGA tool can be downloaded from Moodle
• Unzip the downloaded archive
• Open the "MUGA_12_full.jar" file using java
• To setup the tool, go to "Select Problem"
• Choose "real coded" and "F3_Shifted Rosenbrock"
• Change "Parameters" to 2
• Select "Simple Population"
• Press "Set Parameters"

Genetic Algorithms Tool Setup

• Select the problem from the available options
• Choose "real coded" and "F4_Shifted_Rastrigin" as a problem example
• Change the number of parameters to 2
• Select "Simple Population" as the population model
• Click "Set Parameters"

Genetic Algorithm Implementation Steps

• The user should go back to the MuGA-Home page
• Then they should click on the Run Genetic Algorithm tab
• Change the default values for the criteria and the population to appropriate values for a small problem
• The population should move to the plot window
• If delay >0, increase the delay to see the population moving faster
• Use the 'setup Statistics' tab to add graphs from the data of several trials
• To step through each stage of the algorithm click start
• The two new windows that appear contain the offspring population and the best value plot

Questions and Investigations

• Vary the Rosenbrock and Rastrigin functions with different numbers of variables
• Focus on mutation probability and selection parameters (tournament size, k value) in the experimentation
• Explore crossover mechanisms, considering the absence of mutation
• Evaluate the fitness of the best individual and the number of generations it takes to obtain it in different iterations
• Analyze how mutation rate and selection pressure influence convergence in the algorithm
• Investigate the robustness of the algorithm to changes in the fitness landscape
• Test the algorithm on the Shifted Sphere, Griewank, and Ackley functions

Swarms

• Swarms are self-organised multi-agent systems with emergent collective behaviour
• A key example of swarming behaviour is bird flocking or fish schooling, governed by simple rules.
• Rules for bird flocking/fish schooling include:
  • Moving away from neighbors if too close
  • Moving closer to neighbors if too far away
  • Aligning with the average orientation of neighbors.
• Parameters affect swarming behaviors, including approaching, separating, and turning ratios.
• Swarm behavior results from simple individual rules.
• Social simulation is based on individuals that are allowed to be different types, but prefer to be surrounded by individuals of similar type. Individuals may move to a location if less than a certain percentage of neighbors have their own color.

Self-Organisation (SO)

• SO systems are self-organised multi-agent systems (swarms) with emergent collective behaviour.
• SO properties are:
  • No external control.
  • Increase in order after perturbations.
  • Adaptability.
  • Interaction.
  • Asynchronism.
• SO mechanisms are:
• Positive feedback (amplifying an effect, examples include: ants recruiting for a food source).
• Negative feedback (stabilizing an effect, examples include: the end of a food source).
• Random fluctuations (noise, examples include: a lost ant may explore).

Ant Colony Optimisation (ACO)

• ACO is a swarm intelligence algorithm
• Problem: Travelling Salesperson Problem (TSP)
• Find the minimum route visiting each city only once
• In Euclidean space: Distance between cities $d_{ij} = [(x_i - x_j)^2 + (y_i - y_j)^2]^{1/2}$
• J_i is a set of cities to visit by ant k, in city i
• Initially, all cities except the starting city (i) in the list

Particle Swarm Optimisation (PSO)

• PSO was proposed in 1995 by Kennedy and Eberhart
• It is a physical particles model inspired in social-psychological theory
• Each particle represents a multi-dimensional point in search space
• It has position and velocity
• It is influenced by own previous behaviour and neighbours’ success

Swarm Optimisation Analysis

• ACO and PSO are models of self-organisation
• Both are robust tools for optimisation
• PSO models are decentralised and have local interaction
• ACO models are decentralised but require global information

Portuguese Studies of Cooperation

• Questions concerning conditions that allow cooperation to emerge spontaneously within societies composed of selfish agents, with or without a central authority.
• Goal is to develop mechanisms for encouraging cooperation in both real and artificial systems to better understand the behaviour of such systems in nature (e.g., birds flocking).
• The analysis from the theory of natural selection points out that cooperative behaviour could be disadvantageous. However, cooperative behaviours exist in nature.
• Examples of cooperative behaviour in nature include alarm calls by birds and monkeys, food sharing in bats.

Game Theory

• Game theory models interactions as games, considering that players are rational.
• Games are represented by payoff matrices.
• Nash Equilibrium (NE) defines a combination of strategies where no player gains advantage by changing their strategy unilaterally. NE can involve mixed strategies.

Prisoner's Dilemma

• A payoff matrix is used to explain the prisoner's dilemma
• Nash Equilibrium is (T, T) - suggesting that cooperation is not rational in the one-shot game.
• However, if the game is repeated, cooperation may be more beneficial.

Snowdrift Game

• A payoff matrix is used to explain the snowdrift game
• Nash Equilibria are (C, T), (T, C), and a combination of mixed strategies that depend on the relative values of the payoffs.
• Pure strategies usually suggest the opposite strategy than the other participant
• A strategy of opposing the other players strategy in a repeated game may result in better payoffs for both participants.

Iterated Prisoner's Dilemma

• Iterated Prisoner's Dilemma (IPD) describes a game played multiple times by players with memory of previous interactions.
• The rational choice for repeated games is to not cooperate.
• However, a strategy of mutual cooperation, like TIT-FOR-TAT, can succeed in IPD.

Axelrod's Tournament

• Researchers submitted strategies to play iterated prisoner's dilemma,
• The simplest strategy, TIT-FOR-TAT, usually performed the best.

TIT-FOR-TAT

• The TIT-FOR-TAT strategy initially cooperates and then mirrors the previous move of its opponent.
• Success depends on:
  • Not being the first to defect.
  • Immediate retaliation for defections.
  • Quickly forgetting previous defections.
  • Possibility of future interactions among players.

Evolutionary Game Theory

• Evolutionary game theory studies cooperation from an evolutionary perspective, including how adaptive strategies spread in a population and how the population adapts to changes in strategies using the principle of replication by comparing fitness.
• It doesn't assume rational agents, but instead fitness describes how adaptive an agent is in different situations.
• The evolution of strategies can be by:
  • Stability analysis
  • Explicit populations and their dynamic properties.

Evolutionary Stable Strategy (ESS)

• A strategy is an evolutionarily stable strategy (ESS) if a population with that strategy cannot be invaded by a rare mutant adopting a different strategy.

Other Ways to Achieve Cooperation

• Cooperation can also come from:
  • Altruism (especially for biological connections)
  • Grouping (allows like entities to interact frequently)
  • Explicit population simulations and applying the replication equation

Replication Equation

• Used in the explicit population simulations of strategies. It's used to compare the evolutionary success of different strategies or groups of agents in the same environment.

Symmetric Games

• In symmetric two-player games, each player performs the same role.
• The payoff matrix is represented by 911, 912, 921, 922

Numerical Results

• Shows how degree centrality affects the average proposal as the value of $α$ changes
• Investigates how $α$ and $M$ values influence the average payoff
• Analyzes the $M$ parameter impact on Lorenz curves, with various choices of $α$

Other Aspects of SO in Peer Production

• Modularity
• Evolution
• Hierarchy Formation
• Size and Free-Riding

Network Types

• Regular networks
• Small-world networks
• Random networks
• Scale-free networks

Community Detection

• An important method for uncovering the organization of networks
• Features include:
  • Highly connected internal nodes
  • Fewer links between different communities

Graph Theory

• Studying networks using graphs
• Nodes are entities like genes, neurons, etc
• Edges describe relations (kin ship, similarity, co-occurrence)
• Relations can be:
  • (non) reciprocal
  • weighted
  • temporal
• Node strength is related to the number of connections it has.

Data Collection

• Data from several medical and political sources
• Networks of disease are used to represent human systems.
• Methods from network science are used to model epidemics.

Information Dynamics

• Information dynamics in Internet-mediated prostitution networks
• Networks of about 6,000 sex workers and approximately 10,000 buyers
• The links represent encounters between buyers and sex workers, and information is exchanged via online posts
• This is an example of a bipartite model
• The model can be used to understand disease transmission, specifically in the context of gonorrhea and HIV.