Nature-Inspired Population-Based Metaheuristics and Optimization Techniques

Population-based metaheuristics Nature-inspired Initialize a population A new population of solutions is generated Integrate the new population into the current one using one these methods by replacement which is a selection process from the new and current solutions Evolutionary Algorithms genetic algorithm Estimation of distribution algorithm (EDA) Scatter search Evolutionary programming- genetic programming Swarm Intelligence Ant colony Particle swarm optimization (PSO) Bee colony Artificial Immune system AIS Continue until a stopping criteria is reached The generation and replacement process could be memoryless or some search memory is used 1

Bee Colony Optimization TSP Lowering makespan is equivalent to the profitability of a food source in terms of distance and sweetness of nectar 5 steps: recruitment, local search, neighborhood shrinking, site abandonment, and global search. The mating process maintains healthy numbers of the reproductive queen, male drones, (to generate new bees- solutions), non reproductive female workers (foragers and scouts), and the new born broods. Maintain a colony of bees (N solutions) where a bee will traverse the entire solution. Generate ns scouts. The scouts (ns N) must visit every node once from the start to the sink Once a feasible solution is found they will return to perform the waggle dance to advertise their finds (evaluate the objective function and rank the best nb ns to the worst ) create a neighborhood The elite nb solutions are kept which recruit new foragers nbf, and the rest ns-nb also recruit nsf foragers but less than nbf. The numbers of recruits depends on fitness function and the size of nb. Here recruit means generate solutions with the neighborhood. Ex use scatter search with neighborhood s centroid. The new recruits (foragers) will search locally within the scout s neighborhood, and foragers that are better than scouts will now become new scouts. Otherwise the neighborhood is shrunk by discarding from ns-nb. Replace ns-nb with new randomly generated solutions and add to N. Maintain size ns at end of each iteration. If the neighborhood is abandoned due to no improvement over a fixed number of iterations then a set of new scouts is generated. Note that N is not a constant = contains nb(some replaced by elite sites foragers) + best foragers from ns-nb sites + scouts 2

Artificial Immune system Mimics biological immune system Immune system is adaptive, parallel, self-organized Representations: components antigens, antibodies, cells, and molecules Affinity: interactions between system components and with the environment. Represented as a similarity or dissimilarity index by using the distance measure Adaptation: Procedures that govern the system Population based AIS clonal and natural selection theory Immune system stimulated by antigens Network based AIS, Negative selection AIS 3

AIS Clonal theory Antibody Affinity Antigen Solution Obj fnc Optimization problem (pattern match for intrusion detection, classifying traffic flow in a network) Reproduction of solutions Cloning Somatic mutation multiple mutation of the solution Affinity maturation Mutation and selection of best solution Receptor editing Diversification 4

Clonal Selection theory For Immune system response to infection Based on the concept of cloning and affinity maturation B and T lymphocytes are selected to destroy the antigens invading the body When an antigen enters the body, the B cells that best bind with the antigens proliferate by cloning. The B cells clone a specific type of antibody The strength of binding is dependent on how well (closely) the paratope on the antibody bind with the epitope of the antigen. This property is called affinity A high rate of somatic mutation is applied to the cloned cell to promote genetic diversity The selection pressure ensures that only cells with higher affinity will survive 5

Clonal Selection theory in Optimization Antibodies and antigens are represented by a string of attributes and are binary, integer or real valued Their matching is performed based on distance metric Euclidean, Manhattan or Hamming represents affinity Generate a population of N antibodies randomly. Select n from N based on a selection criteria and clone and mutate to construct new candidate population of antibodies The number of clones Nc generated is proportional to their affinities The mutation rate is inversely proportional to their affinities Receptor editing leads to extreme mutation, which results in diversification Evaluate the cloned antibodies Replace the worst members of the n with the best from the above process 6