数学建模 遗传算法解决TSP问题相关论文
机床与液压#2006 No 8
!19!
题转化为两个问题来求解,若维数太高还可以转化为多个问题来求解。如下面问题
minf(x1,x2,x3,x4,x5,x6)若由粒子群算法得一局部最优解x
1*
1*
1*
中的个体通常参照群体中目前处于最优位置的个体和自身曾经达到的最优位置调整下一步的搜寻;从而设
计了粒子群优化算法。
对问题(3)基本PSO算法迭代公式如下:
vid(t+1)= 1vid(t)+ 1 1(pid(t)-xid(t))+ 2 2(pgd(t)-xid(t))
xid(t+1)=xid(t)+vid(t+1)
其中:i和d分别为粒子的序号和分量编号,
(4)(5)v和x
(7)=(x1,
1*
x2, ,x6),以下给出两个策略把高维优化转化为低维优化:
1*
(1)随机取几个分量,例如取3个分量x1,x2,x4,下一步就求
minf(x1,x2,x3,x4,x5,x6)
1*
2*
1*
2*
2*
1*
1*
1*
1*
1*
分别为每个粒子的速度和位置,t为迭代计算的步
数, 1、 1、 2为系统的控制参数, 1和 2均为(0,1)区间上的随机数,pid是粒子i到目前为止得到的最好结果的位置,pgd是到目前为止整个粒子群体得到的最好结果所对应的粒子的位置。由此可看出粒子群算法的基本思想就是每个个体充分利用群体的智能与自身的智能不断地调整学习,最终得到满意的解。
(8)
1*
再用粒子群算法求解,又得到一局部最优解(x1,x2,x3,x4,x5,x6),这时又可以再随机选取一些分量,也可以交替选取,即上次选取1、2、4分量,这次就选取3、5、6,这样交替进行;这样又得到新的优化问题,一直这样下去。
(2)随机取一些分量,把原问题分为以下几个小问题: 可分为minf(x1,x2,x3,x4,x5,x6)与minf(x1,x2,x3,x4,x5,x6),也可以把所有的3个变量的所有可能形式即C6=20中全部写出,从而原问题化为20个小优化问题,%若觉得维数太高,可以任取p(p(比较大)个分量,把原问题转化为几个优化问题,也可列出所有Cn个优化问题。把分得到的几个优化问题再用粒子群算法求解,把求得的几个最优解进行比较,取出最好的作为下一步的局部最优解,又进行下一步的分解,一直这样下去。
p
3
1*
1*
1*
1*
1*
1*
2 2 动态规划粒子群优化算法(DPSO)
动态规划方法(DynamicProgramming)是求解优化问题的一种经典确定算法,该方法是基于最优性原理与无后效性而提出的用于求解多阶段决策过程的算法。最优性原理为:最优决策的任何截断仍是最优的;无后性为:在任何阶段处的截断,后面阶段所作的决策只与该阶段的初态有关,而与其它无关。动态规划方法通过最优性原理与无后效性,把优化的问题进行阶段分解,从而起到把复杂的问题简单化,使计
[5,6]
算量大为减少。
粒子群优化算法是一种全局优化算法,但在求解高维函数时存在不足,而对维数较低时确实非常有效。动态规划方法的求解过程是把复杂问题逐一枝解为较简单的问题,最后得到问题的解,正因这一特点,若将此特点与粒子群算法特性相结合,则必将能改进粒子群算法的优化性能。
***
对于问题(3),设(x1,x2, ,xn)是最优解,有类似动态规划的结论成立
**
minf(x1,x2, ,xn)=minf(x1,x2, ,xi, ,xi,*
,xi,xi, ,xn)(6)
从而把一个n维的优化问题转化为(n-m)维的优化问题,因而在优化过程中当粒子群优化算法陷入局部最优,而此时局部最优解中又有些分量已是问题的最优解的分量,若能把这些分量定下来,由式(6)就可以把原来的高维优化问题转化为低维的优化问题,再由粒子群优化算法对低维优化问题的有效性就可以求出原问题的最优解;但局部最优解中哪些分量已是最优解的分量,是很难判断的,在实际操作中具体可以采用不同的策略进行判定;如在局部最优解中随机取出一些分量认为是最优解分量;也可以交,1
2
m
m+1
2 3 动态规划粒子群优化算法的计算步骤
对于式(3)的优化问题,算法的主要步骤为:Step1:随机产生规模为m的初始种群,一般m&10。
Step2:按PSO方法计算一定的代数之后或计算到出现连续几代之内目标值均无改善之后,设这时得
*000
到的最优解为x=(x1,x2, ,xn)。
*n
Step3:在最优解x中随机选出[]个分量,
2
000
设为xi,xi, ,xi。
1
2
||
n
Step4:用PSO方法求解以下两个优化问题minf(x)=f(x1,x2, ,xi, ,xi, ,xi
1
2
000
|
n
, ,(9), ,(10)
xn)
与minf(x)=f(x1,x2,xn)
这两个优化问题一个是n-[维的优化函数。
,xi, xi, xi
1
2
||
n
nn]维、一个是[]22
Step5:取出这两个优化问题所得的结果中最优的那个解为当前的最优解x,检查是否满足终止条,,*
: 水库优化调度是一个典型的 具有多约束条件的、 动态的、 非线性的优化问题...动态规划粒子群算法解 PCB 数控钻孔 最佳走刀路线问题 [ J]. 机床与液压, ...
陈光明 基于数控加工的工艺设计原则及方法研究[期刊论文]-制造业自动化 2005(09) 3.莫愿斌;陈德钊 动态规划粒子群算法解PCB数控钻孔最佳走刀路线问题[期刊论文]...
智能优化算法(蚁群算法和粒子群算法)_交通运输_工程科技_专业资料。主要介绍智能...提出了许多用以解决 复杂优化问题的新方法,如进化规划、进化策略、 遗传算法等,...
基于改进粒子群算法的智能机器人路径规划摘 要:针对机器人路径规划问题,为了使机器人能在较短的时间里,经过最短的 路径,且较平滑的从起始位置运动到目标位置。本...
20 08 双层 规划 问题 的粒子 群 算法研 究李相 勇 , ? 田 澎 , ( 上海 交通 大学安 泰经 济 与管 理学 院 摘要 : 上海 . 20 0 5 2 ) 提 ...
暂无评价 5页 7下载券 适于车辆路径规划的改进... 暂无评价 6页 免费喜欢...粒子群优化算法 计算车辆路径问题摘要粒子群优化算法中,粒子群由多个粒子组成,...
关键词:粒子群算法 PCB实时检 该付费资源由维普网提供 中国最大最早的专业...如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处...
24, No. 3 March 2007 基于量子粒子群算法求解整数规划* 刘静, 须文波, ...出了 量子 粒子 群优 化算 法( QPSO) , 并用于 求解 整数 规划 问题 。...
另一方面又具有进化算法的特 点,和遗传算法、进化策略、进化规划等算法有 相似...粒子群优化算法伪代码 //说明:本例以求问题最小值为目标 //参数:N为群体规模...
热门文档