● 模拟退火算法
模拟退火算法(SA)是一种启发式算法,它是受加热金属的退火过程所启发而提出的一种求解组合优化问题的一种逼近算法.在某个温度下,金属分子停留在能量小的状态的概率比停留在能量大的状态的概率要大.SA在求复杂优化问题最好解中已显示出其非常的有效性自K i rkpatrick于1983将Metropolis在1953年提出的模拟退火思想应用到组合优化问题以来,受到大家的普遍关注.
算法(模拟退火算法)
Step 1.初始化可行解和温度.
Step 2.根据Boltzmann概率退火.
Step 3.重复第二步直到稳定状态.
Step 4.降温.
Step 5.重复第二步至第四步直到满足终止条件或直到给定的步数.
Step 6.输出最好的解作为最优解.
初始化过程
1.随机产生一个可行解S0.
2.理论上,初始温度应保证平稳分布中每一状态的概率相等,即
其中△fij=f(sj)-f(si)
如可取t0=K△0(右下角),K为充分大的数而
算法(初始温度算法)
Step 1.给定一个常数T;温度to ;常数Xo(如0.9); Ro = 0.
Step 2.在这个温度退火L步.记接受状态的个数为L',计算Rk= L'/L.
Step 3.如果|Rk一X0|<
,停止.否则,如果R(k-1),Rk
=X0,则k = k+l, to = to一T,返回step 2;如果R(k-1)>=X0,Rk<=X0,则k=k+l,to=to+T/2,返回step 2;如果R(k-1)<=X0,Rk>=X0,则k=k+l,to=to一T/2,返回step2 .
退火
退火过程就是在一给定温度下,由一个状态变到另一个状态,每一个状态到达的次数服从一个概率分布,即基于Metropolis接受准则的过程,该过程达到平稳时停止.在状态sj时,产生的状态sj被接受的概率为
降温:
一种方法:
另一种:
其中M为温度下降的总次数.
技术问题:
解的达形式和邻域结构:
要求解的表达形式简洁明了易于操作;邻域中每个邻居都是可行解,解空间中任何两状态可达.
对TSP问题,解S可表示为城市的一个排序.解的邻域可用不同的操作算子定义,如
● 互换操作:即随机交换解码中两不同的字符位置
● 逆序操作:即将解码中两不同的随机位置间的字符串逆序
● 插入操作:即随机选择某个点插入到串中的不同随机位置如果邻域中有不是可行解的邻居,可用罚值法,将其视为可行解,目标值为一个充分大的数.但该法的缺陷是扩大了搜索区域,从而使计算时间增加.
内循环终止准则:
常用的有
● 1.固定步数2.连续若干步的目标值变化较小3.由接受和拒绝的比率控制迭代步数
外循环终止准则:
常用的有1.设置终止温度的i-值(比较小的正数)2.设置循环总数3.连续若干步搜索到的最优解不再改进4.设置接受概率
遗传算法
遗传算法(GA)是一种解优化问题的随机搜索方法,它借助于生物进化中的自然选择和遗传(即适者生存)的规律.
基本遗传算法
算法(基本遗传算法)
Step 1.随机初始化pop_size个染色体.Step 2.用交叉算法更新染色体.Step 3.用变异算法更新染色体.Step 4.计算所有染色体的目标值.Step 5.根据目标值计算每个染色体的适应度.Step 6.通过轮盘赌的方法选择染色体.Step 7.重复第二至第六步直到终止条件满足.Step 8.输出最好的染色体作为最优解.
为利于遗传算法的计算,首先要对解进行编码,编码后的解称为染色体.对于约束优化问题,遗传算法是在染色体中进行操作,而把操作结果解码后去检验其可行性.
收敛性:
模板理论
● 设遗传算法中群体和种群的维数相等,为一个偶数
维,且不随代数的变化而变化;
● 适应函数直接选用目标函数;
● 种群中的个体通过轮盘赌的方式选取,即第i个染
色体被选中的概率为
种群中的一对个体采用随机交叉的方式产生下一代;每一个基因有相同的变异概率.
模板定理
我们有
如果
则从概率意义来说,每代中具有H模板的染色体个数将随代数t的增加而增加.
收敛定理
● 若变异概率0设计.如对于连续优化问题,可预估一个含有最优解的区域 (如超平面).在这个区域中随机产生一个点,然后检验这个解的可行性.如是可行的,则接受为染色体;如不可行,则重新在那个区域中随机产生一个点直到是可行点为止.重复刚才的过程pop_size次得到pop_size个初始染色体.
群体的规模
1. 群体的规模可以设定为个体编码长度数的一个线性倍数2.群体的规模可以是一个给定数3.群体的规模也可以是变化的.当连续多代没能改变解的性能,则可扩大群体的规模;若解的改进非常好,则可以减少群体的规模.
评价函数
评价函数Eval ( V)是根据每个染色体V的适应函数fitness( V)而得到与其他染色体的比例关系,可用它决定该染色体被选为种群的概率.如
选择过程
交叉运算
1. 常用方法一一双亲双子2.变化交叉位法3.多交叉位法4.双亲单子法5.显性遗传法6.单亲遗传法*
对于根据问题确定的编码,交叉运算可用如下之方法1.随机选一个交叉位,父代交叉位前的基因分别继承给两个后代,两后代之后的基因分别按对方基因顺.序选取不重基因2.不变位法
变异运算
蚁群优化算法Ant Colony Optimization
Algorith ms(ACOA)是求解组合优化问题的一种启发式算法,它受蚂蚁的社会行为而启发.在ACOA,计算信息是靠赋予一群人工蚂蚁信息素而实现的.ACOA由orig。于1992年提出,在求解许多复杂优化问题中宣示出良好的鲁棒性和通用性.
问题描述
蚂蚁在寻找食物过程中,会在他们经过的地方留下信息素.这些物质能影响后来蚂蚁的行动,后到的蚂蚁选择有较多这些物质的路径的可能性比有较少这些物质的路径的可能性大得多.后到的蚂蚁留下的信息素会对原有的信息素进行加强.
考虑极小化问题(s, f, 偶米噶),其中s是定义域,f是目标函数,而(偶米噶)约束集.组合优化问题(S, f,偶米噶)也可描述为一个有向图问题G=(C,L,T),其中C为顶点集,L为连接顶点C的边集,而T是一个称为信息素(淘)的向量.
基本蚁群算法
算法(蚁群优化算法)
Step 1.初始化所有的信息素具有同样的量.
Step 2.根据信息素构造人工蚂蚁行动路线(解)
Step 3.重复第二步直至所有蚂蚁完成一次行动.
Step 4.根据当前最好解更新路径上的信息素.
Step 5.重复第二至第四步直至终止条件满足.
Step 6.输出最好解作为最优解.
信息素更新
在t时刻,设S^是目前为止的最好可行解,而St是当前t时刻的最好可行解.设f(s^)和f (st)是对应的目标函数值.
如果,f (St)
Eo,那么k=0,
到第二步------Step 8.结束.
继续阅读