A brief introduction to the Python genetic algorithm Geatpy toolbox

This article brings you relevant knowledge about Python. It mainly introduces the use of the Python genetic algorithm Geatpy toolbox. Friends in need can refer to it. I hope it can be helpful. To help, let’s take a look below.

[Related recommendations: Python3 video tutorial]

1. What is a genetic algorithm?

Genetic algorithm is a type of search algorithm constructed artificially by simulating the mechanism of biological genetics and natural selection. To a certain extent, genetic algorithm is a mathematical simulation of the biological evolution process. The survival process of biological populations generally follows Darwinian evolution principles. Individuals in the population are selected or eliminated by nature based on their ability to adapt to the environment. The result of the evolutionary process is reflected in the structure of the individual. Its chromosome contains several genes. The corresponding connection between phenotype and genotype reflects the logical relationship between the external characteristics and internal mechanism of the individual. Adapt to the natural environment through crossover and mutation between individuals. Biological chromosomes are represented mathematically or computerically as a string of numbers, still called chromosomes, sometimes also called individuals; adaptability is measured by a numerical value corresponding to a chromosome; the selection or elimination of chromosomes is based on the problem faced. Find the maximum or minimum.

2. Genetic Algorithm Library Geatpy

2.1 Introduction to Genetic Algorithm Toolbox Geatpy Parameters

API official reference document

population parameter[Important attributes: Chrom, Phen, Objv, CV, FitnV]

• sizes: int - population size, that is, population number of individuals.
• ChromNum: int - The number of chromosomes, that is, how many chromosomes each individual has.
• Encoding: str - chromosome encoding method, 'BG': binary/Gray encoding; 'RI': real integer encoding, that is, a mixed encoding of real numbers and integers; 'P': permutation encoding
• Field : array - decoding matrix
• Chrom : array - population chromosome matrix, each row corresponds to a chromosome of an individual.
• Lind : int - population chromosome length.
• ObjV: array - population objective function value matrix, each row corresponds to an individual's objective function value, each column corresponds to a target
• FitnV: array - population individual fitness column vector, each The element corresponds to the fitness of an individual, and the minimum fitness is 0
• CV: array - CV (Constraint Violation Value) is a matrix used to quantitatively describe the degree of violation of constraint conditions. Each row corresponds to an individual, and each column corresponds to A constraint
• Phen: array - the population phenotype matrix (that is, the matrix composed of the decision variables represented by each chromosome of the population after decoding).
• If constraints are set based on the feasibility rule through the CV matrix, then the inequality constraints need to be ≤, and the equality constraints need to be passed into abs() (because it follows the principle that the larger the value, the smaller the fitness)

• lbin and ubin (decision variable range) in ea.Problem.init() Boundary matrix) represents the opening and closing of the range interval, 1 closed 0 open interval

Geatpy result parameter introduction

success: True or False, indicates whether the algorithm was successfully solved.

stopMsg: A string that stores the reason for stopping the algorithm.

optPop: Population object that stores the algorithm solution results. If there is no feasible solution, optPop.sizes=0. optPop.Phen is the decision variable matrix, optPop.ObjV is the objective function value matrix.

lastPop: The last generation population object after the algorithm evolution is completed.

Vars: equal to optPop.Phen, here is the optimal solution. If there is no feasible solution, Vars=None.

ObjV: equal to optPop.ObjV, here is the objective function value corresponding to the optimal solution. If there is no feasible solution, ObjV=None.

CV: equal to optPop.CV, here is the constraint violation degree matrix corresponding to the optimal solution. If there is no feasible solution, CV=None.

startTime: Program execution start time.

endTime: Program execution end time.

executeTime: The time taken by the algorithm.

nfev: Number of algorithm evaluations

gd: (Available only when multi-objective optimization is given and the theoretical optimal solution is given) GD index value .

igd: (Available only when multi-objective optimization is given and the theoretical optimal solution is given) IGD indicator value.

hv: (only for multi-objective optimization) HV indicator value.

spacing: (only for multi-objective optimization) Spacing indicator value.

3. Best Practices

3.1 Code Example|Parameter Template

Solution Set:

header_regex = '|'.join(['{}'] * len(headers))
header_str = header_regex.format(*[str(key).center(width) for key, width in zip(headers, widths)])
print("=" * len(header_str))
            print(header_str)
            print("-" * len(header_str))

gen: evolutionary algebra
eval: record number of evaluations
f\_opt: objective function value of the contemporary optimal individual
f \_max=Maximum function value of the contemporary population                              
f\_min  Minimum  f\_avg  :  average                                                                                                                                                                                                            

Use the geatpy library to solve the shortest path of a directed acyclic graph

Code [Shortest Path] 1: Use the geatpy library

import numpy as np
import geatpy as ea
class MyProblem(ea.Problem):  # 继承Problem父类
    def __init__(self):
        name = 'Shortest_Path'  # 初始化name（函数名称，可以随意设置）
        M = 1  # 初始化M（目标维数）
        maxormins = [1]  # 初始化maxormins（目标最小最大化标记列表，1：最小化该目标；-1：最大化该目标）
        Dim = 10  # 初始化Dim（决策变量维数）
        varTypes = [1] * Dim  # 初始化varTypes（决策变量的类型，元素为0表示对应的变量是连续的；1表示是离散的）
        lb = [0] * Dim  # 决策变量下界
        ub = [9] * Dim  # 决策变量上界
        lbin = [1] * Dim  # 决策变量下边界 1表示闭合区间，0表示开区间
        ubin = [1] * Dim  # 决策变量上边界
        # 调用父类构造方法完成实例化
        ea.Problem.__init__(self, name, M, maxormins, Dim, varTypes, lb, ub, lbin, ubin)
        # 设置每一个结点下一步可达的结点（结点从1开始数，因此列表nodes的第0号元素设为空列表表示无意义）
        self.nodes = [[], [2, 3], [3, 4, 5], [5, 6], [7, 8], [4, 6], [7, 9], [8, 9], [9, 10], [10]]
        # 设置有向图中各条边的权重
        self.weights = {'(1, 2)': 36, '(1, 3)': 27, '(2, 4)': 18, '(2, 5)': 20, '(2, 3)': 13, '(3, 5)': 12,
                        '(3, 6)': 23,
                        '(4, 7)': 11, '(4, 8)': 32, '(5, 4)': 16, '(5, 6)': 30, '(6, 7)': 12, '(6, 9)': 38,
                        '(7, 8)': 20,
                        '(7, 9)': 32, '(8, 9)': 15, '(8, 10)': 24, '(9, 10)': 13}
    def decode(self, priority):  # 将优先级编码的染色体解码得到一条从节点1到节点10的可行路径
        edges = []  # 存储边
        path = [1]  # 结点1是路径起点
        while not path[-1] == 10:  # 开始从起点走到终点
            currentNode = path[-1]  # 得到当前所在的结点编号
            nextNodes = self.nodes[currentNode]  # 获取下一步可达的结点组成的列表
            chooseNode = nextNodes[np.argmax(
                priority[np.array(nextNodes) - 1])]  # 从NextNodes中选择优先级更高的结点作为下一步要访问的结点，因为结点从1数起，而下标从0数起，因此要减去1
            path.append(chooseNode)
            edges.append((currentNode, chooseNode))
        return path, edges
    def aimFunc(self, pop):  # 目标函数
        pop.ObjV = np.zeros((pop.sizes, 1))  # 初始化ObjV
        for i in range(pop.sizes):  # 遍历种群的每个个体，分别计算各个个体的目标函数值
            priority = pop.Phen[i, :]
            path, edges = self.decode(priority)  # 将优先级编码的染色体解码得到访问路径及经过的边
            pathLen = 0
            for edge in edges:
                key = str(edge)  # 根据路径得到键值，以便根据键值找到路径对应的长度
                if not key in self.weights:
                    raise RuntimeError("Error in aimFunc: The path is invalid. (当前路径是无效的。)", path)
                pathLen += self.weights[key]  # 将该段路径长度加入
            pop.ObjV[i] = pathLen  # 计算目标函数值，赋值给pop种群对象的ObjV属性
## 执行脚本
if __name__ == "__main__":
    # 实例化问题对象
    problem = MyProblem()
    # 构建算法
    algorithm = ea.soea_EGA_templet(problem,
                                    ea.Population(Encoding='RI', NIND=4),
                                    MAXGEN=10,  # 最大进化代数
                                    logTras=1)  # 表示每隔多少代记录一次日志信息
    # 求解
    res = ea.optimize(algorithm, verbose=True, drawing=1, outputMsg=False, drawLog=False, saveFlag=True,
                      dirName='result')
    print('最短路程为：%s' % (res['ObjV'][0][0]))
    print('最佳路线为：')
    best_journey, edges = problem.decode(res['Vars'][0])
    for i in range(len(best_journey)):
        print(int(best_journey[i]), end=' ')
    print()

Python3 video tutorial

The above is the detailed content of A brief introduction to the Python genetic algorithm Geatpy toolbox. For more information, please follow other related articles on the PHP Chinese website!