TP Genetic Algorithms PDF

TP Genetic Algorithms Rob Mills, Nuno Garcia, Luís Correia The MUGA Tool Download MUGA from Moodle Unzip the archive Open "MUGA_12_full.jar" o java jar "MUGA_12_full.jar" Setup Go to Select Problem Choose “real coded” and “F3_Shifted_Rosenbrock”...

TP Genetic Algorithms Rob Mills, Nuno Garcia, Luís Correia The MUGA Tool Download MUGA from Moodle Unzip the archive Open "MUGA_12_full.jar" o java jar "MUGA_12_full.jar" Setup Go to Select Problem Choose “real coded” and “F3_Shifted_Rosenbrock” Change “Parameters” to 2 Select “simple population” Press “set parameters”  On the “Main Population” window o Choose “GR phenotype” o You can change the view with click and hold/drag (angle=left, zoom=right) Go back to “MuGA - Home” Click “Setup Solver” On the “Selection” tab, choose “Tournament” On the “Recombination” tab, choose “NoRecombination” On “Mutation” tab, choose “real.RCGA_Gauss” Leave Replacement and Rescaling to default values.  Go back to “MuGA - Home” and click Run Experiment with different stop criteria o Since we are testing a small problem the default value will be too high, change to 40 generations Watch the population moving in the plot window o increase the delay > 0 (100 250 is good); else set to 0 to allow fastest running speed In this dialog, you can o step through each phase of the GA (selection, variation, replacement), o step through a whole generation’s worth [“next generation”] o or let the algorithm progress until the stop criterion/a Two new windows appear when you click “Start” o Offspring Population and the plot of Best Value. You can see the progress of the population You can also add new graphs to be created using the “setup statistics” tab Questions algorithm choices, problem sizes Choose the Rosenbrock function, and after the Rastrigin With 2 variables (to facilitate inspection) and then with 10 variables (to gather results) Only use mutation and selection; vary the probability of mutation, p_m Then also use crossover, with much smaller p_m Use roulette selection, and tournament selection (2 g21 e g12 > g22 ➔ S1 domina S2 S1 S2 2. g11 < g21 e g12 < g22 ➔ S2 domina S1 S1 S2 equilíbrio estável Equilíbrio instável  Equação de replicação 3. g11 > g21 e g12 < g22 ➔ S1 e S2 são bi‐estáveis S1 S2 (g22 – g12) / (g11 – g12 – g21 + g22)  Equação de replicação 4. g11 < g21 e g12 > g22 ➔ S1 e S2 coexistem S1 S2 (g22 – g12) / (g11 – g12 – g21 + g22) 5. g11 = g21 e g12 = g22 ➔ Deriva aleatória  Equação de replicação‐ exemplos Dilema do Prisioneiro C T – T domina C 3 0 T 5 1 Snowdric C T – C e T coexistem C 3 2 T 4 0  Estratégias reacDvas estocásDcas Cada estratégia é representada por S(p, q) onde – p: probabilidade de cooperar se o outro cooperou – q: probabilidade de cooperar se o outro traiu A população é iniciada aleatoriamente O que acontece se for uDlizada a equação de replicação?  Estratégias reacDvas estocásDcas Dilema do Prisioneiro Na maior parte das vezes, T ≈ (0, 0) domina Por vezes, o TIT‐FOR‐TAT ≈ (1, 0), suplanta T Mas, uma população de TFTs tem um mau desempenho na presença de erros O TFT é depois subsDtuído pelo TFT‐Generoso ≈ (1, ω)  Estratégias estocásDcas As estratégias reacDvas têm em conta apenas a acção anterior do outro jogador Vamos agora considerar o conjunto de todas as estratégias estocásDcas com memória 1 (p1, p2, p3, p4) probabilidade de cooperar se as acções anteriores foram (CC, CT, TC, TT)  Estratégias estocásDcas Dilema do Prisioneiro Começa por acontecer o mesmo que acontece para as estratégias reacDvas Depois, o TFT‐Generoso é subsDtuído pela estratégia PAVLOV ≈ (1, 0, 0, 1)  Estratégias estocásDcas O TFT é um bom catalisador da cooperação, mas… – Não é capaz de corrigir erros – Não impede uma deriva para a estratégia Cooperar incondicionalmente A estratégia PAVLOV não tem estes problemas  Jogos evolucionários espaciais Em muitas situações não é realista considerar população panmícDcas Em muitas situações cada agente interage apenas com um pequeno sub‐conjunto da população  Jogos evolucionários espaciais Uma população de agentes que interage durante muitas iterações Em cada iteração, cada agente joga o jogo com os seus vizinhos (topologia de interacção) Em cada iteração, um ou mais agentes actualizam a sua estratégia (dinâmica de actualização)  Jogos evolucionários espaciais A actualização de estratégias é realizada uDlizando uma regra de transição que pode modelar: – O facto de os agentes tentarem imitar os vizinhos mais bem sucedidos – Um processo evoluDvo em que as estratégias menos bem sucedidas tendem a ser subsDtuídas por estratégias mais bem sucedidas  JEEs ‐ Topologias de interacção Grelhas regulares Redes de escala livre Redes de mundo pequeno  JEEs – Dinâmicas de actualização Dinâmica síncrona: em cada iteração todos os agentes actualizam a sua estratégia em simultâneo Dinâmica sequencial: em cada iteração apenas um agente actualiza a sua estratégia Dinâmica assíncrona estocásDca: em cada iteração cada agente é actualizado com probabilidade α (taxa de sincronismo)  JEEs – Regras de transição Melhor vizinho: imitar sempre o vizinho mais bem sucedido Regra proporcional: a probabilidade de um vizinho ser imitado é proporcional ao seu ganho Equação de replicação: escolher um vizinho v aleatoriamente; Se gv > gi, imitar v com probabilidade  Cooperação em populações estruturadas Em 1992 MarDn Nowak e Robert May mostraram que é possível a sobrevivência de cooperadores incondicionais sem memória Condições: Dilema do Prisioneiro, grelha regular 2D, dinâmica síncrona, regra melhor vizinho  Cooperação em populações estruturadas A estrutura espacial permite que os cooperadores se organizem em grupos Deste modo, os cooperadores interagem sobretudo entre si As redes de escala livre suportam mais cooperadores (J. Pacheco (UL) e F. F. Santos)  Influência da dinâmica de actualização Em geral, uma dinâmica assíncrona suporta mais cooperadores Com uma dinâmica síncrona acontecem mais trocas de estratégia entre agentes vizinhos As trocas de estratégia destroem os grupos de cooperadores Topologias de interacção dinâmicas A topologia de interacção pode mudar com o tempo A escolha de parceiros pode ser baseada, por exemplo – Na experiência individual – Na informação fornecida por outros agentes (reputação)  Reputação ‐ exemplo eBay: após uma interacção, cada agente pode avaliar o comportamento do seu parceiro – A avaliação pode ser 1 (posiDva), 0 (neutral) ou ‐1 (negaDva) – A reputação de um agente é a soma dos valores dados nos úlDmos seis meses  Reputação Problemas que podem ocorrer em sistemas de reputação – Os agentes podem menDr, por exemplo, para proteger ou prejudicar outros agentes – Coligação de agentes de modo a forjar a sua reputação – Um agente com má reputação pode sair do sistema e entrar com outra idenDdade  Bibliografia The EvoluDon of CooperaDon, Robert Axelrod, Penguin Science EvoluDonary Dynamics, MarDn Nowak, Harvard University Press EvoluDonary games on graphs, György Szabó e Gábor Fáth Review on computaDonal trust and reputaDon models, Jordi Sabater and Carles Sierra  Complex Networks and Systems Artificial Life 2022/2023 Andreia Sofia Teixeira https://andreiasofiateixeira.com Andreia Sofia Teixeira - Complex Networks and Systems Andreia Sofia Teixeira - Complex Networks and Systems  Complex: definition (Dictionary.com) composed of many interconnected parts; compound; composite: a complex highway system characterized by a very complicated or involved arrangement of parts, units, etc.: complex machinery so complicated or intricate as to be hard to understand or deal with: a complex problem Andreia Sofia Teixeira - Complex Networks and Systems  Complex Systems and Networks Behind each complex system there is an intricate network that is able to express the interactions between the system’s components: The network encoding the interactions between genes, proteins, and metabolites integrates these components into live cells. The very existence of this cellular network is a prerequisite of life. The wiring diagram capturing the connections between neurons, called the neural network, holds the key to our understanding of how the brain functions and to our consciousness. The sum of all professional, friendship, and family ties, often called the social network, is the fabric of the society and determines the spread of knowledge, behavior and resources. Communication networks, describing which communication devices interact with each other, through wired internet connections or wireless links, are at the heart of the modern communication system. The power grid, a network of generators and transmission lines, supplies with energy virtually all modern technology. Trade networks maintain our ability to exchange goods and services, being responsible for the material prosperity that the world has enjoyed since WWII. Andreia Sofia Teixeira - Complex Networks and Systems http://networksciencebook.com/chapter/1#networks  Network Science Interdisciplinary Empirical, Data Driven Quantitative and Mathematical Computational Impactful Social Economic Health Security Epidemics Neuroscience And so much more… Andreia Sofia Teixeira - Complex Networks and Systems  The Seven Bridges of Königsberg The problem was to devise a walk through the city that would cross each of those bridges once and only once. Andreia Sofia Teixeira - Complex Networks and Systems  Networks (Graph Theory) Each node is an entity: - Gene, Neuron, Person, Concept, Trait Each link is a relation - Regulation, Activation, Social Kinship, Similarity, Co-Occurrence These relations can be: - (Non) Reciprocal, weighted, temporal The strength of a node is related with the number of connections it has. The betweenness is related with how many shortest paths go through that node or edge. Andreia Sofia Teixeira - Complex Networks and Systems  Networks (Graph Theory) Andreia Sofia Teixeira - Complex Networks and Systems http://networksciencebook.com/chapter/2#summary2  Networks – Random and Small World The Watts-Strogatz Small World model (Nature ‘98) Andreia Sofia Teixeira - Complex Networks and Systems  Small-World and the Six Degrees of Separation Full documentary about the six degrees of separation: https://www.cornell.edu/video/emergence-of-network-science Andreia Sofia Teixeira - Complex Networks and Systems http://networksciencebook.com/chapter/3#small-worlds  Networks – Trees and Scale-Free Tree Scale Free Network Andreia Sofia Teixeira - Complex Networks and Systems  What does it mean… Scale-Free? Andreia Sofia Teixeira - Complex Networks and Systems  What does it mean… Scale-Free? Andreia Sofia Teixeira - Complex Networks and Systems http://networksciencebook.com/chapter/4#hubs  What does it mean… Scale-Free? Andreia Sofia Teixeira - Complex Networks and Systems http://networksciencebook.com/chapter/4#hubs  Centrality Measures Andreia Sofia Teixeira - Complex Networks and Systems Centrality Measures Centrality measures help us identify the core entities and relations in complex networks. There are centrality measures focused on the nodes and on the links. These measures are usually used in algorithms to identify core structures of the networks, or to test their resilience to perturbations (e.g., removal of nodes or links – aka percolation). We will go over the simplest ones.  Centrality Measures Andreia Sofia Teixeira - Complex Networks and Systems https://doi.org/10.3389/fnins.2019.00585  Spanning Edge Betweenness – Phylogenetic Trees Andreia Sofia Teixeira - Complex Networks and Systems https://doi.org/10.1371/journal.pone.0119315  Link centrality in Network Connectivity Andreia Sofia Teixeira - Complex Networks and Systems h"ps://doi.org/10.1007/978-3-319-30569-1_1  Communities and Clustering US Political Blogs Disease Networks (build with PC) Karate Club* Andreia Sofia Teixeira - Complex Networks and Systems This networks and its community detection is so famous that there is even a prize: https://networkkarate.tumblr.com/  Communities and Clustering 𝐿! = 𝑁𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑙𝑖𝑛𝑘𝑠 𝑖𝑛 𝑐𝑙𝑢𝑠𝑡𝑒𝑟 𝑐 𝑘! = 𝑡𝑜𝑡𝑎𝑙 𝑑𝑒𝑔𝑟𝑒𝑒 𝑜𝑓 𝑛𝑜𝑑𝑒𝑠 𝑖𝑛 𝑐𝑙𝑢𝑠𝑡𝑒𝑟 𝑐 Andreia Sofia Teixeira - Complex Networks and Systems  Communities and Clustering Community detection is important to uncover the organization of a network. There are two main features in community detection algorithms: Communities have many internal links, so their nodes are highly connected. There are few links connecting different communities, so they are well separated. Algorithms: There is a considerable amount of different approaches to identify communities or network partitions: They can be based on modularity maximization, spectral clustering, hierarchical clustering, link betweenness, label propagation, stochastic block model, and many more… Andreia Sofia Teixeira - Complex Networks and Systems  Communities and Clustering Andreia Sofia Teixeira - Complex Networks and Systems https://www.nature.com/articles/s41567-022-01716-7  Resources Gephi (gephi.org) NetLogo (ccl.northwestern.edu/netlogo) Python Python and the NetworkX (networkx.readthedocs.org) module. You can follow one or both of two approaches: There are currently several free services to run Jupyter notebooks in the cloud, including: Google Colab (colab.research.google.com) Binder (mybinder.org) Kaggle Kernels (www.kaggle.com/kernels) Azure Notebooks (notebooks.azure.com) Datalore (datalore.io) Gryd (gryd.us) Andreia Sofia Teixeira - Complex Networks and Systems  Resources Gephi (gephi.org) NetLogo (ccl.northwestern.edu/netlogo) Andreia Sofia Teixeira - Complex Networks and Systems  Applications Andreia Sofia Teixeira - Complex Networks and Systems  Bacterial Populations Evolution Andreia Sofia Teixeira - Complex Networks and Systems  Motivation Evolution and Propagation Epidemics and outbreaks. Observed population structure of several important human pathogens can be explained using a simple evolutionary model - based on neutral mutational drift and modulated by recombination. Validation of methods with real populations is not possible as only rather small samples of the real pathogen population are available and accessible. Andreia Sofia Teixeira - Complex Networks and Systems  Motivation Evolution and Propagation How can we obtain larger samples of bacterial populations? Are all populations well-mixed? (No, they are not!) What is the impact of host contact network topologies, and associated transmission ratios, on bacterial population evolution and genetic diversity? What happens in the absence of selection phenomena? Andreia Sofia Teixeira - Complex Networks and Systems  Problem/Solution To observe phenomena of near real scale is necessary to simulate models close to real scales. We use large graphs to represent interactions between bacteria populations. Each node is a population. Each link represents a connection between populations in which transmissions of bacteria can occur. Andreia Sofia Teixeira - Complex Networks and Systems  Biological Model Infinite Allelle Model/Wright Fisher Model Andreia Sofia Teixeira - Complex Networks and Systems  Simulation and Computational Models Host Contact Population Network Evolutionary Exchanges Model Spark GraphX One Iterative Composable API Andreia Sofia Teixeira - Complex Networks and Systems  Simulation and Computational Models Simulation Process in Each Node Population Individual Profile Allele Mutation Rate Recombination Rate Network Simulation Process Edge List Exchange Frequency Transmission ratios Andreia Sofia Teixeira - Complex Networks and Systems  Experimental Setup We run simulations for 2500 generations (with cycles of 25 evolutions followed by 1 exchange between nodes), and compute the Simpsons Index of Diversity (SID) for each node. The population size was 1000 per node, with each simulation containing 1 000 000 individuals. The mutation and recombination rate took values of 0.0001, 0.001 and 0.01. Andreia Sofia Teixeira - Complex Networks and Systems  Preliminary Results in a small network Andreia Sofia Teixeira - Complex Networks and Systems  Results – Genetic Diversity Evaluation Andreia Sofia Teixeira - Complex Networks and Systems  Main Observations Fluctuations in genetic diversity can be an artifact of neutral drift only, without selection pressure in heterogenous networks. This can erroneously be attributed to selection events, suggesting that distinction between drift and selection is essential if we aim to understand natural evolutionary processes. Teixeira, A. S., Monteiro, P. T., Carriço, J. A., Santos, F. C., & Francisco, A. P. (2017, August). Using Spark and GraphX to Parallelize Large-Scale Simulations of Bacterial Populations over Host Contact Networks. In International Conference on Algorithms and Architectures for Parallel Processing (pp. 591-600). Springer, Cham. Teixeira, A. S., Monteiro, P. T., Carriço, J. A., Santos, F. C., & Francisco, A. P. (2018). Large-scale simulations of bacterial populations over complex networks. Journal of Computational Biology, 25(8), 850-861. Andreia Sofia Teixeira - Complex Networks and Systems  Brain Andreia Sofia Teixeira - Complex Networks and Systems Andreia Sofia Teixeira - Complex Networks and Systems  Building Structural Connectivity (SC) Networks Andreia Sofia Teixeira - Complex Networks and Systems https://onlinelibrary.wiley.com/doi/full/10.1002/nbm.3752 Andreia Sofia Teixeira - Complex Networks and Systems DOI:10.1038/s42254-019-0040-8  Identifying network properties and mapping to brain regions Andreia Sofia Teixeira - Complex Networks and Systems  Health Andreia Sofia Teixeira - Complex Networks and Systems  Example Comorbidity Networks — Pearson’s Correla:on > 0.1 Andreia Sofia Teixeira - Complex Networks and Systems  The human disease network Andreia Sofia Teixeira - Complex Networks and Systems https://www.pnas.org/content/104/21/8685  Visual Analytics cycle applied to Network Medicine Andreia Sofia Teixeira - Complex Networks and Systems https://doi.org/10.1002/wsbm.1489  Epidemics Andreia Sofia Teixeira - Complex Networks and Systems  Modelling a Pandemic Andreia Sofia Teixeira - Complex Networks and Systems Image from http://networksciencebook.com/  Modelling a Pandemic Andreia Sofia Teixeira - Complex Networks and Systems Image from http://networksciencebook.com/  Modelling a Pandemic Andreia Sofia Teixeira - Complex Networks and Systems  Modelling a Pandemic Andreia Sofia Teixeira - Complex Networks and Systems  Evaluating the impact of PrEP on HIV and Gonorrhea on a networked population of female sex workers In collaboration with Alberto Bracci, Pau Casanova, Iacopo Iacopini, Andreia Sofia Teixeira - Complex Networks and Systems Benjamin Steinegger, Alberto Antonioni, Eugenio Valdano  Measures to prevent HIV transmission Andreia Sofia Teixeira - Complex Networks and Systems  Key factors evaluating a PrEP rollout Andreia Sofia Teixeira - Complex Networks and Systems  Risk compensa