优化算法之遗传算法GA:
遗传算法(Genetic Algorithm,GA)最早是由美国的 John holland提出,主要模拟生物进化论的自然选择和遗传学机理生成计算模型,是一种通过模拟自然进化过程搜索最优解的方法,将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时,相对一些常规的优化算法,通常能够较快地获得较好的优化结果。遗传算法已被人们广泛地应用于组合优化、机器学习和人工生命等领域。
GA特点:
优点:
- 根据适应度保留某些候选解,放弃其他候选解。
- 从串集开始搜索,而不是从单个解开始。
- 同时处理群体中的多个个体,从而大大降低出现局部最优的情况。
- 具有自组织、自适应和自学习性。
缺点:
- 效率比其他传统的优化方法低。
- 易过早收敛。
遗传算法流程:
(1)初始化:设置进化代数计数器t=0,设置最大进化代数T,随机生成M个个体作为初始群体P(0)。
(2)个体评价:计算群体P(t)中各个个体的适应度。
(3)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
(4)交叉运算:将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。
(5)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。
(6)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出,终止计算。
遗传算法部分代码:
clear;
close all;
% 概率和
cumulative_probabilities = cumsum((parent_number:-1:1) / sum(parent_number:-1:1)); %是长度为parent_number
% 最优适应度值
best_fitness = ones(maximal_generation, 1);
% elite
elite = zeros(maximal_generation, number_of_variables);
% child_number
child_number = population_size - parent_number; % 每一代子女的数目
% 种群初始化
population = rand(population_size, number_of_variables);
last_generation = 0;
% 循环寻优
for generation = 1 : maximal_generation % 演化开始
cost = feval(fitness_function, population); % 计算所有适应度
[cost, index] = sort(cost); % 排序
% 对应交叉概率
population = population(index(1:parent_number), :); % 保留个体
best_fitness(generati
绘图:
适应度情况:
![](https://img-blog.csdnimg.cn/a6cb755bb9b940ec9621cf3f9aa8abb8.jpeg)
最优解情况:
![](https://img-blog.csdnimg.cn/b04496baf73d44a4b195a2061351a520.jpeg)