发布时间：2024-03-12 11:22:33 浏览：
一、优化问题：
优化：是应用数学的一个分支，主要研究在特定情况下最大化或最小化某一特定函数。
优化算法是在建立了数学模型之后不能求偏微分 or 不能通过求导的方式求得最小值时，采用一些优化算法能够解决问题。
二、遗传算法
遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化论过程的一种搜索（寻优）算法，在人工系统中实现特定目标的优化。实质是通过群体搜索技术，根据适者生存逐代进化最终得到最优解。
遗传算法必须做以下操作：初始群体的产生、求每一个个体的适应度、根据适者生存选择优良个体（选择）、选出的优良个体配对产生下一代群体（交叉、变异）、循环进行逐代进化直到满足中止条件。
| 生物遗传概念 | 遗传算法中的作用 |
|---|---|
| 适者生存 | 算法停止时，最优目标值的可行解有最大的可能被留住 |
| 个体 | 可行解 |
| 染色体 | 可行解的编码 |
| 基因 | 可行解中每一分量的特征 |
| 适应性 | 适应度函数 |
| 种群 | 根据适应度函数选取的一组可行解 |
| 交配 | 通过交配原则产生一组新的可行解 |
| 变异 | 编码的某一分量发生变化的过程 |
1.遗传算法原理
（1）选择操作：
轮盘法，基于适应度比例的选择策略，个体被选中的概率为：个体被选中的概率 = 个体适应度函数值 / 所有个体适应度函数值总和
P
i
=
f
i
∑
j
=
1
n
f
j
P_{i}=\frac{f_{i}}{\sum_{j=1}^n f_{j}}
Pi?=∑j=1n?fj?fi??
（2）交叉操作：
交叉操作采用单点交叉，第个染色体 ak 和第个染色体 al 在位的交叉操作方法为，b为[0, 1]随机数：
a
k
j
=
a
k
j
(
1
?
b
)
+
a
l
j
(
b
)
a_{kj}=a_{kj}(1-b)+a_{lj}(b)
akj?=akj?(1?b)+alj?(b)
a l j = a l j ( 1 ? b ) + a k j ( b ) a_{lj}=a_{lj}(1-b)+a_{kj}(b) alj?=alj?(1?b)+akj?(b)
（3）变异操作：
变异是实现群体多样性的一种手段，也是全局寻优的保证。
第个个体的第个基因 aij 进行变异操作的方法为，r为[0, 1]随机数，gen为当前迭代次数，genmax为最大迭代次数：
a
i
j
=
a
i
j
?
(
a
i
j
?
a
m
i
n
)
?
(
1
?
G
(
g
e
n
)
)
,
r
<
=
0.5
a_{ij}=a_{ij}-(a_{ij}-a_{min})*(1-G(gen)),~~r<=0.5
aij?=aij??(aij??amin?)?(1?G(gen)),??r<=0.5
a i j = a i j + ( a m a x ? a i j ) ? ( 1 ? G ( g e n ) ) , r > = 0.5 a_{ij}=a_{ij}+(a_{max}-a_{ij})*(1-G(gen)),~~r>=0.5 aij?=aij?+(amax??aij?)?(1?G(gen)),??r>=0.5
其中关于G（gen）函数有：
G
(
g
e
n
)
=
r
(
1
?
g
e
n
g
e
n
m
a
x
)
2
G(gen)=r(1-\frac{gen}{genmax})^2
G(gen)=r(1?genmaxgen?)2
2.遗传算法MATLAB实现
程序结构：
（1）主程序Genetic.m
用于求解的遗传算法参数设定如下：
种群大小最大代数
交叉率交叉概率为1能保证种群的充分进化
变异率一般而言，变异发生的可能性较小
（2）初始化群体Code.m
（3）目标函数func.m
（4）选择操作Select.m
（5）交叉操作Cross.m
（6）变异操作Mutation.m
（7）test.m
3.遗传算法的改进
遗传算法的缺陷出现在交叉、变异操作，这些操作很可能会将优秀基因个体给变异掉（丢失最优解）。
算法改进：采用遗传算法精英库的策略：将交叉、突变后的子代与父代同时保留，对其进行排序比较留下精英部分。
三、粒子群算法
粒子群算法主要是在模拟鸟类觅食的行为：一群鸟在随机搜索食物（在这个区域里只有一块食物、所有鸟都不知道食物位置、但他们知道离食物还有多远），找到食物的最优策略采用搜索离食物最近的鸟的周围区域——粒子群算法。
食物：目标函数的最小值、鸟的位置：代表决策变量、
粒子群算法必须做以下操作：初始群体的产生、计算粒子目标函数值、确定全局最优粒子、更新速度和位置（核心操作）、粒子是否收敛（是否满足中止条件）。
1.粒子群算法原理
（1）速度与位置的更新操作：
由n只鸟组成的种群，其中第i只鸟的位置可表示为；其速度为，则第次迭代中鸟类的位置与速度可更新为：
时刻的位置 = 时刻位置+时刻速度方向
时刻速度 = ω常数 * 时刻速度（速度惯性向） + 个体自信方向 + 全局最优方向
X
i
t
?
+
?
1
=
X
i
t
+
V
i
t
?
+
?
1
X^{t~+~1}_i=X^t_i+V^{t~+~1}_i
Xit?+?1?=Xit?+Vit?+?1?
V i t ? + ? 1 = ω V i t + c 1 r 1 ( P i b e s t t ? X i t ) + c 2 r 2 ( G b e s t t ? X i t ) V^{t~+~1}_i=ωV^t_i+c_{1}r_{1}(P^t_{ibest}-X^t_i)+c_{2}r_{2}(G^t_{best}-X^t_i) Vit?+?1?=ωVit?+c1?r1?(Pibestt??Xit?)+c2?r2?(Gbestt??Xit?)
（2）区分全局最优与个体最优的概念：
全局最优：在一个种群中，所有的鸟在某一代中 or 在某个时刻中所能找到的最优值，为1组数字（位置）。
个体最优：针对每一个体，某一只鸟从第1代到第 代这个过程中，该鸟所找到的最优值，为n组数字（位置）。
补充：详细可使用matlab查看粒子群算法运行中产生的参数gbest和pbest变量，进行进一步理解
2.粒子群算法MATLAB实现
程序结构：
（1）主程序PSO.m：
（2）目标函数func.m：
3.粒子群算法的改进
粒子群算法受到初始种群生成的影响较严重，如果初始种群生成不恰当将导致结果陷入局部最优解，而不是全局最优解。
算法改进：为避免粒子群陷入局部最优解，类比遗传算法应考虑为粒子群算法也加入基因变异的操作（粒子位置重新分布）。
4.补充：优化问题约束条件的处理
对于约束条件（包括等式约束、不等式约束）的处理，使用惩罚函数进行操作：
（1）惩罚函数：
用于解决约束条件下的最优化问题，通过惩罚函数可以将现有约束的目标函数转化为无约束的目标函数。
f
(
x
)
′
=
f
(
x
)
+
C
f(x)'=f(x)+C
f(x)′=f(x)+C
其中C为一个非常大的常数，相对于遗传算法、粒子群算法而言当个体被加上常数C时，就会被排除在最优解之外。
具体在粒子群算法上对程序进行修改后的结果为：
四、多目标优化问题
在实际问题中大都具有多个目标且需要同时满足，即在同一问题模型中同时存在几个非线性目标，而这些目标函数需要同时进行问题优化处理，而这些目标又往往是互相冲突的（必要），这类问题被称为多目标优化问题。
补充：多目标优化问题的解往往是多个解
1.多目标优化
（1）多目标优化关键概念：
point1：支配
在多目标优化问题中，如果个体p至少有一个目标比个体q好，而且个体p的所有目标都不比个体q差，那么称个体p支配个体q（p>=q）。
如下图图例所示，图中可以看出个体A、B完全支配个体C（个体C将被淘汰），而个体A、B之间不存在支配关系。
point2：序值
如果p支配q，那么p的序值比q低。如果p和q互补支配，那么p和q有相同的序值。
point3：拥挤距离
拥挤距离用来计算某前端中的与该前端中之间的距离，用以表征个体间的拥挤程度。
（2）多目标较单目标优化问题的难点：
- 全局最优与局部最优的选择
- 目标函数的计算（多个最优值的筛选与删除），涉及支配、拥挤距离问题，具体实现见代码演示
2.多目标优化代码实现：
以下的多目标优化问题使用粒子群优化算法解决，作为案例
程序结构：
函数调用结构：
注意：同层次间的函数还存在相互调用的关系，图示中不做详细表示
（1）主程序main.m：
（2）多目标优化粒子群算法MOPSO.m：
（3）根据网格质量选区最优selectLeader.m：
（4）更新精英库updateRepository.m：
如何更新精英库涉及支配问题、拥挤距离问题
（5）检测越界函数checkBoundaries.m：
（6）检测支配函数checkDomination.m：
（7）dominates.m：
（8）删除精英库个体函数deleteFromRepository.m：
（9）粒子群算法优化*：变异操作mutation.m：
（10）更新网格操作updateGrid.m：
疑问：多目标优化问题粒子算法实现最后的结果与正确结果相差较大？
3.多目标优化结果处理
注明：程序应用请标明出处，为防止代码查重本文请适当进行代码修改
