人工智能优化算法.ppt

《人工智能优化算法.ppt》由会员分享，可在线阅读，更多相关《人工智能优化算法.ppt（43页珍藏版）》请在优知文库上搜索。

1、优化问题的分类单目标优化和多目标优化优化目标的个数约束优化和非约束优化有无约束条件连续优化和离散优化优化的变量多目标优化12( ),( ),.,( )kf xfxfx目标目标 通常而言，这通常而言，这k个目标函个目标函数是相互冲突矛盾的，即不能同时达到最大数是相互冲突矛盾的，即不能同时达到最大值或者最小值，这需要寻找一个折衷的解。值或者最小值，这需要寻找一个折衷的解。通常称这些解为通常称这些解为Pareto最优解。最优解。 有些文章中采取，有些文章中采取，Y=a*U+b*V, a+b=1，但个人认为这是没有任何理论依据的。但个人认为这是没有任何理论依据的。 多目标优化问题是优化理论研究的热点。

2、多目标优化问题是优化理论研究的热点。12( )( ),( ),.,( )kf xf xfxfx21( )f xx22( )2fxxf2f1Pareto front solutiondominated solutionThe Pareto Front for a Two-Objective Optimization Problems约束优化问题( )( )( )Ffpxxx12( )(,)( )0,1,( )0,1,nggghfx xxgmnhmnnnxxxxmm最小化 ，使得 处理方法：罚函数方法处理方法：罚函数方法max 0,( )1,()( )( )+1,+()mgmmgghgmnphmn

3、nnxxx如果不等式如果等式经典的算法遗传算法(GA)量子遗传算法(GQA)粒子群算法(PSO)人工蜂群算法(ABC)量子粒子群算法(QPSO)膜优化理论多目标优化算法遗传算法(Genetic Algorithm) 遗传算法(Genetic Algorithm，GA)是建立在自然选择和群体遗传学基础上的搜索方法，是由美国Michigan大学的Holland教授首先提出并发展起来的。 核心思想：初始种群产生之后，按照“适者生存”和“优胜劣汰”的原理，逐代演化产生出越来越好的近似解。 现在的研究方向多为遗传算法与其它智能优化算法结合以及小生境遗传算法。交叉和变异算子p 单点交叉p 随机变异 (Bo

4、undary Mutation):,.,.,.,.,21212121nkkknkkkyyyyyyxxxxxxyxcrossing point at kth position父代子代,.,.,.,.,21212121nkkknkkkxxxyyyyyyxxxyxmutating point at kth position,.,.,2121nkkkxxxxxxx父代子代,.,.,2121nkkkxxxxxxx交叉算子 交叉交叉 (单点交叉) 这里应用单点交叉，这也是在遗传算法中应用最广泛的交叉方这里应用单点交叉，这也是在遗传算法中应用最广泛的交叉方式，另外还有双点交叉，多点交叉，均匀交叉等。式，另外

5、还有双点交叉，多点交叉，均匀交叉等。 将父代交叉点后的基因交换位置，从而产生子代的基因。将父代交叉点后的基因交换位置，从而产生子代的基因。 交叉点是随机产生的，图示为产生的在交叉点为交叉点是随机产生的，图示为产生的在交叉点为17处的交叉过处的交叉过程。程。v1 = 100110110100101101000000010111001 v2 = 001110101110011000000010101001000c1 = 100110110100101100000010101001000 c2 = 001110101110011001000000010111001在17位基因处交叉变异算子 变异变异

6、 根据变异概率确定基因是否变异。 假设染色体 v1 的第16位变异，则变异的过程如下。 由于该基因为1，则变异之后变为0。 要注意的是，变异概率相对于交叉概率是很小的。v1 = 100110110100101101000000010111001 c1 = 100110110100101001000000010111001 在16基因位开始变异选择算子 经典的选择算法：轮盘赌选择经典的选择算法：轮盘赌选择适应度高的个体被选择为后代的概率高，而适应度低的个体被选择为后代的概率低这也正是体现了达尔文的进化论“优胜劣汰，适者生存”的思想伪代码初始化种群For generation=1:max_gene

7、ration for ind=1:n/2 轮盘赌选择个体 if U(0,1)Pc 随机产生 for p=sm 1212,niiiimXxxxx xxx其中 ,ijx x1,2,smipjpxxjpipxx end end for t=1:m if U(0,1)Pm end end end 执行精英保留策略end ititxxjtjtxx量子遗传算法量子遗传算法是量子计算和遗传算法相结合的产物，其关键步骤包括染色体编码、种群测量、种群更新等。在QGA中，染色体编码采用量子位来实现。量子位与经典位的不同之处在于它可以落在和之外的线性组合态，其状态通常表示为： | 0|1 221设一个染色体包含位量

8、子位，则其编码形式为量子旋转门的更新操作如下所示测量过程如下： 1212llqcossinsincosijijijijijijijij(,)ijijijijs 221,()0,()ijijijrxr量子旋转门的选取Han, K.H. and Kim, J.H. Genetic quantum algorithm and its application to combinatorial optimization problem C. Proceedings of the 2000 IEEE International Conference on Evolutionary Computation.

9、 USA: IEEE Press, 2000:1354-1360. 伪代码t=0initialize Q(t)make P(t) by observing Q(t) statesrepair P(t)evaluate P(t)store the best solution b among P(t)while (t MAX-GEN) do t=t+1 make P(t) by observing Q(t - 1) states repair P(t) evaluate P(t) update Q(t) store the best solution b among P(t)end粒子群Parti

10、cle Swarm Optimization群体智能是由大量简单个体相互交流和协作涌现出的智能行为。PSO源于对鸟群和鱼群等觅食和迁徙等行为的模拟，是群体智能的重要代表。PSO的提出者粒子群算法(PSO)PSO迭代公式1 12 2()() (1) (2)VwVcr pxc r gxxx V 惯性项认知项社会项pw : 惯性权重pc1, c2 : 学习因子 pr1, r2 : 0,1区间内随机数 pP ：个体最优位置； g ：全局最优位置PSO求解Schwefel函数1( )() sin() 500500 ( )=418.9829; =420.9687, i=1:n niiiiif xxxxf

11、xnx最小化问题其中最优解粒子群收敛过程示意图求解结果迭代次数种群最优解0416.2455995515.74879610759.40400615793.73201920834.813763100837.9115355000837.965771真实解837.9658PSO的优点模型简单计算简单全局优化能力强具有高维多目标优化能力伪代码创建并初始化一个M维的粒子群Repeat for 每个粒子i=1N If /设置个体的最佳位置 end If /设置全局的最佳位置 end end for每个粒子i=1N 更新粒子的速度 更新粒子的位置 endUntil 终止条件为真( )()iif xf yiiy

12、x( )()iif xf yiiyx人工蜂群算法(ABC) 人工蜂群算法是模仿蜜蜂行为提出的一种优化方法。主要特点是不需要了解问题的特殊信息，只需要对问题进行优劣的比较，通过各人工蜂个体的局部寻优行为，最终在群体中使全局最优值突现出来，有着较快的收敛速度。Karaboga提出了人工蜂群算法(artificial bee colony algorithm)。 食物源的数目工蜂的数目观察蜂的数目侦察蜂的数目1工蜂寻找食物源的位置若则更新食物源的位置否则，食物源的位置保持不变。观察蜂选择工蜂公式实际是轮盘赌选择机制。(1)( )( )iicccD. Karaboga, B. Basturk, On

13、The Performance Of Artificial Bee Colony (ABC) Algorithm, Applied Soft Computing,Volume 8, Issue 1, January 2008, Pages 687-697. B. Basturk, D. Karaboga, An artificial bee colony (ABC) algorithm fornumeric function optimization, in: IEEE Swarm Intelligence Symposium2006, May 1214, Indianapolis, IN,

14、USA, 2006.( )( )( )ikccc(1)( )iiFcFc/21( )( )iiNkkFcPFc观察蜂根据轮盘赌选择的工蜂的食物源位置，来更新自己的食物源位置。观察蜂的位置更新过程跟工蜂的位置更新过程类似。当工蜂或者观察蜂的食物源位置经过“limit”次后仍然没有更新，则工蜂或者观察蜂变为侦察蜂，随机选择食物源的位置。人工蜂群算法是一种比较有效的算法，这是因为此算法存在侦察蜂，能够在收敛的同时进行适度发散。算法流程InitializeREPEAT Move the employed bees onto their food sources and determine their

15、nectar amounts. Move the onlookers onto the food sources and determine their nectar amounts. Move the scouts for searching new food sources. Memorize the best food source found so far. UNTIL (requirements are met)人工蜂群算法收敛示意图人工蜂群算法量子粒子群算法Hongyuan GAO, Jinlong CAO. A simple quantum-inspired particle s

16、warm optimization and its application. International Journal ofAdvancement in Computing Technology . Ei源期刊已录用量子粒子的量子位置定义为 1212ll112()()tttttidididgdide pxepx2111211 () ,( )abs(cos1 ()sin),ttttidididgdtidttttididididvpxprcvvv若且其它1 211 21,()0,()tidtidtidrvxrv量子粒子群算法流程 步骤1：初始化量子粒子群，包括随机选择量子粒子的位置, 量子粒子的速度和量子粒子的局部最优解。 步骤2：对量子粒子进行适应度评价，从而得到全局最优解。 步骤3：更新量子粒子的量子速度和位置。 步骤4：对于量子粒子的新位置，计算适应度值。 步骤5：更新量子粒子的局部最优解，同时找到全局的最优解作为进化的目标。 步骤6：如果进化并没有终止(通常由预先设定的最大循环次数决定)，返回步骤3, 否则，算法终止。 Benchmark函数测试试验 21111001100cos