Shulou(Shulou.com)06/01 Report--

This article will explain in detail several different selection operators in genetic algorithms and how to use Python to achieve, the content of the article is of high quality, so the editor will share it for you to do a reference. I hope you will have a certain understanding of the relevant knowledge after reading this article.

Selection operator in genetic algorithm

Genetic algorithm (genetic algorithms, GAs) is an adaptive heuristic search algorithm, which imitates the principle of "survival of the fittest" in Darwinian evolution, and finally obtains the optimal solution of the optimization objective. The following figure describes a simple genetic algorithm flow:

There are many species selection methods that need to be crossed in the population, and the selection of an appropriate selection strategy will have a great impact on the overall performance of genetic algorithms. If the diversity of a selection algorithm is reduced, it will lead to the premature convergence of the population to the local optimal point rather than the global optimal point we want, that is, the so-called "precocious". If the selection strategy is too divergent, it will make it difficult for the algorithm to converge to the optimal point. Therefore, in these two points, we need to balance in order to make the genetic algorithm converge to the global optimal point in an efficient way.

Different selection strategies

In this part, I mainly summarize four different selection strategies and implement them in the form of gaft plug-in Python.

The selection operator determines which individuals will be selected from the population to reproduce new individuals in the next generation of population. Its main principles are:

The better is an individual; the higher is its chance of being a parent

The selection operator introduces the fitness function into the iteration of genetic algorithm, because the fitness function calibrates an important criterion of whether an individual is "good" or not. However, the selection process can not only rely on the fitness function, because the optimal species in a population is not necessarily near the global optimal point. Therefore, we should also give relatively good individuals a chance to reproduce and avoid precocious puberty.

The probability of ai being selected is good, so we can write this algorithm as an operator that can be executed in gaft.

Python

From random import random

From bisect import bisect_right

From itertools import accumulate

From... plugin_interfaces.operators.selection import GASelection

Class RouletteWheelSelection (GASelection):

Def _ init__ (self):

''

Selection operator with fitness proportionate selection (FPS) or

So-called roulette-wheel selection implementation.

''

Pass

Def select (self, population, fitness):

''

Select a pair of parent using FPS algorithm.

''

# Normalize fitness values for all individuals.

Fit = [fitness (indv) for indv in population.individuals]

Min_fit = min (fit)

Fit = [(I-min_fit) for i in fit]

# Create roulette wheel.

Sum_fit = sum (fit)

Wheel = list (accumulate ([i/sum_fit for i in fit]))

# Select a father and a mother.

Father_idx = bisect_right (wheel, random ())

Father = population [popularity _ idx]

Mother_idx = (father_idx + 1)% len (wheel)

Mother = population [popularity _ idx]

Return father, mother

The process is mainly divided into the following:

Inherit the GASelection class

Implement the select method

The parameters of select are GAPopulation instance and fitness function.

Select two species that need to reproduce according to the algorithm and return them.

Linear Ranking Selection

The following two selection strategies are based on sorting. The first basic roulette selection algorithm mentioned above has a disadvantage, that is, if the fitness value of an individual is 0, the probability of being selected will be 0. This individual will not be able to produce offspring. So we need a sort-based algorithm to arrange the corresponding selection probability for each individual.

In Linear Ranking Selection, the individuals in the population are first sorted according to the value of fitness, and then all individuals are given a serial number, the best individual is N, the probability of being selected is Pmax, the serial number of the worst individual is 1, and the probability of being selected is Pmin, so the probability of other individuals among them can be obtained according to the following formula:

Implementation code:

Python

From random import random

From itertools import accumulate

From bisect import bisect_right

From... plugin_interfaces.operators.selection import GASelection

Class LinearRankingSelection (GASelection):

Def _ _ init__ (self, pmin=0.1, pmax=0.9):

''

Selection operator using Linear Ranking selection method.

Reference: Baker J E. Adaptive selection methods for genetic

Algorithms[C] / / Proceedings of an International Conference on Genetic

Algorithms and their applications. 1985: 101,111.

''

# Selection probabilities for the worst and best individuals.

Self.pmin, self.pmax = pmin, pmax

Def select (self, population, fitness):

''

Select a pair of parent individuals using linear ranking method.

''

# Individual number.

NP = len (population)

# Add rank to all individuals in population.

Sorted_indvs = sorted (population.individuals, key=fitness, reverse=True)

# Assign selection probabilities linearly.

# NOTE: Here the rank i belongs to {1,..., N}

P = lambda I: (self.pmin + (self.pmax-self.pmin) * (iMur1) / (NP-1))

Probabilities = [self.pmin] + [p (I) for i in range (2, NP)] + [self.pmax]

# Normalize probabilities.

Psum = sum (probabilities)

Wheel = list (accumulate ([p/psum for p in probabilities]))

# Select parents.

Father_idx = bisect_right (wheel, random ())

Father = population [popularity _ idx]

Mother_idx = (father_idx + 1)% len (wheel)

Mother = population [popularity _ idx]

Return father, mother

Cdn2.b0.upaiyun.com/2017/09/eff96de9a902d02b9f89266bd3adbdba.png "alt=" WX20170919-222353 "2x" br= "table="tbody="tr="td="data-settings=" show "eeeeee=">

The selection strategy in this paper implements the corresponding operators according to the requirements of the interface. These operators are also put into the GAFT as the built-in operators of the GAFT framework, and the children's shoes using GAFT can be used directly.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.