·110· 智能系统学报 第9卷 研究和改进可以归纳为以下几方面：1)操作算子的 1]为交叉概率，i=1,2,…,P,j=1,2,…,no 改进：2)进化参数的自适应调整：3)多种群：4)混合 4)选择操作。 算法[2这些改进的算法虽然起到了一定的效果， 在差分进化算法中，选择操作采取优选策略，在 但在求解一些复杂优化问题时仍显得不够理想.针 变异操作和交叉操作完成后均进行选择操作，即只 对大规模欺骗函数和等级问题这类一般优化算法难 有当新产生的子代个体优于父代个体时才会保留， 以求解的高维复杂优化问题，本文将模拟退火算子 否则父代个体将继续保留在下一代中。 嵌入到差分进化算法的循环中，提出了二者相结合 1.2模拟退火算法原理及操作 的混合差分进化算法，以提高求解精度，新算法既保 模拟退火算法来源于固体退火原理，通过降温 留了差分进化算法具有较强的搜索能力，又克服了 来控制算法的搜索过程。模拟退火算法对当前解重 在复杂优化问题的求解上过早收敛而陷入局部解、 复如下过程：产生新解→计算目标函数差→接受或 进化后期收敛慢及求解精度不高的缺点。 舍弃，并在此过程中逐步衰减温度值，算法终止时， 即得到近似最优解。 1 差分进化算法与模拟退火算法 在模拟退火算法中，对个体L:按式(4)或者式 1.1差分进化算法原理及操作 (5)产生新个体。 本文是对欺骗函数和等级问题进行优化实验， 1)方式1。 根据所求解问题的特点，算法采用二进制编码方式。 L=(l1,l2,…,l4,…,lm,…,ln） 差分进化算法的基本原理与遗传算法类似，所不同 (4) L=(l1,h2,…,…,l4,…,ln) 的是，在遗传操作中采用种群个体间的差分向量进 式中：L为当前种群中的个体，L"为新产生的个 行变异，这充分利用了不可行解所携带的重要信息， 体，n为个体的编码长度，1<k<m<n。 减小了陷入局部最优解的机率。 2)方式2。 1)种群初始化。 设原个体L=(l1,l2,…,n),产生的新个体为 设L,=(,5,…,)为一个n维向量，即种群 a=(a1,a2,…,a.),随机数p=rand(0,1)(0和1之 中的一个个体，其中编码长度为n,种群大小为P, 间的随机小数)，则产生新个体方式如下： 种群第1代个体按式(1)随机产生： (14-11,pP =rand[0,1],i=1,2,…,P,j=1,2,…,n(1) (5) 其他 式中：rand[0,1]随机产生0或者1，个体为随机产 生的二进制串。初始化种群时产生种群大小为P, 式中：Pm∈[0,1]，新个体L"=a,1<j<no 为了对解空间进行充分的搜索，这2种方式都 编码长度为n的个体。 会被使用，在算法运行过程中随机选择其中的一种 2)变异操作。 算法的变异方式是在种群中随机选取2个不同 方式来产生新个体。新个体产生后计算适应度 的个体，将其向量差取绝对值后与待变异的个体进 f(L)和新旧个体间的适应度增量△E=f(L")- 行向量叠加，变异方式如式(2)所示： f八L:),并计算p=ex邓(-△E/T),按概率p选用或者 是舍弃新个体，重复上述过程一定次数后选择新搜 L+1=Lg-|L8-LgI川， 索到的适应度高的个体进入下一代。 i≠a≠b≠c,i=1,2,…,P (2) 式中：L是g+1代种群中第i个要变异的个体， 2混合差分进化算法 L:、L、L是g代种群中的3个互不相同的个体，由 混合差分进化算法是差分进化算法和模拟退火 于是二进制编码，因此差分向量取绝对值。 算法的合理组合，首先由一组随机产生的初始解开 3)交叉操作。 始搜索，通过带有精英保留策略的遗传操作产生新 交叉操作是在种群中随机选择2个不同的个 个体，然后对每一个新个体进行独立的模拟退火操 体，按式(3)产生新一代个体。 作，将操作完成后生成的个体作为混合算法的下一 L&u,rand≥P。 (3) 代个体，并进行退温操作，经过若干次迭代后，最终 (L,其他 选择种群中最优解作为所求问题的解。混合差分进 式中：rand为[0,1]内均匀分布的随机数，P。∈[0， 化算法流程如图1所示。研究和改进可以归纳为以下几方面：１）操作算子的 改进；２）进化参数的自适应调整；３）多种群；４）混合 算法［２⁃１１］ ．这些改进的算法虽然起到了一定的效果， 但在求解一些复杂优化问题时仍显得不够理想．针 对大规模欺骗函数和等级问题这类一般优化算法难 以求解的高维复杂优化问题，本文将模拟退火算子 嵌入到差分进化算法的循环中，提出了二者相结合 的混合差分进化算法，以提高求解精度，新算法既保 留了差分进化算法具有较强的搜索能力，又克服了 在复杂优化问题的求解上过早收敛而陷入局部解、 进化后期收敛慢及求解精度不高的缺点。 １ 差分进化算法与模拟退火算法 １．１ 差分进化算法原理及操作 本文是对欺骗函数和等级问题进行优化实验， 根据所求解问题的特点，算法采用二进制编码方式。 差分进化算法的基本原理与遗传算法类似，所不同 的是，在遗传操作中采用种群个体间的差分向量进 行变异，这充分利用了不可行解所携带的重要信息， 减小了陷入局部最优解的机率。 １）种群初始化。 设 Ｌｉ ＝ （ｌ ｉ １ ，ｌ ｉ ２ ，…，ｌ ｉ ｎ ） 为一个 ｎ 维向量，即种群 中的一个个体，其中编码长度为 ｎ，种群大小为 Ｐ， 种群第 １ 代个体按式（１）随机产生： ｌ ｉ ｊ ＝ ｒａｎｄ［０，１］，ｉ ＝ １，２，…，Ｐ，ｊ ＝ １，２，…，ｎ （１） 式中：ｒａｎｄ［０，１］随机产生 ０ 或者 １，个体为随机产 生的二进制串。 初始化种群时产生种群大小为 Ｐ， 编码长度为 ｎ 的个体。 ２）变异操作。 算法的变异方式是在种群中随机选取 ２ 个不同 的个体，将其向量差取绝对值后与待变异的个体进 行向量叠加，变异方式如式（２）所示： Ｌ ｇ＋１ ｉ ＝｜ Ｌ ｇ ａ －｜ Ｌ ｇ ｂ － Ｌ ｇ ｃ ｜ ｜ ， ｉ ≠ ａ ≠ ｂ ≠ ｃ， ｉ ＝ １，２，…，Ｐ （２） 式中： Ｌ ｇ＋１ ｉ 是 ｇ＋１ 代种群中第 ｉ 个要变异的个体， Ｌ ｇ ａ 、Ｌ ｇ ｂ、Ｌ ｇ ｃ 是 ｇ 代种群中的 ３ 个互不相同的个体，由 于是二进制编码，因此差分向量取绝对值。 ３）交叉操作。 交叉操作是在种群中随机选择 ２ 个不同的个 体，按式（３）产生新一代个体。 Ｌ ｇ＋１ ｉ，ｊ ＝ Ｌ ｇ ａ，ｊ，ｒａｎｄ ≥ Ｐｃ Ｌ ｇ { ｂ，ｊ， 其他 （３） 式中：ｒａｎｄ 为［０，１］内均匀分布的随机数，Ｐｃ∈［０， １］为交叉概率，ｉ ＝ １，２，…，Ｐ， ｊ ＝ １，２，…，ｎ。 ４）选择操作。 在差分进化算法中，选择操作采取优选策略，在 变异操作和交叉操作完成后均进行选择操作，即只 有当新产生的子代个体优于父代个体时才会保留， 否则父代个体将继续保留在下一代中。 １．２ 模拟退火算法原理及操作 模拟退火算法来源于固体退火原理，通过降温 来控制算法的搜索过程。 模拟退火算法对当前解重 复如下过程：产生新解→计算目标函数差→接受或 舍弃，并在此过程中逐步衰减温度值，算法终止时， 即得到近似最优解。 在模拟退火算法中，对个体 Ｌｉ按式（４）或者式 （５）产生新个体。 １）方式 １。 Ｌｉ ＝ （ｌ １ ，ｌ ２ ，…，ｌ ｋ，…，ｌｍ ，…，ｌ ｎ ） Ｌ ｎｅｗ ｉ ＝ （ｌ １ ，ｌ ２ ，…，ｌｍ ，…，ｌ ｋ，…，ｌ ｎ ） （４） 式中：Ｌｉ为当前种群中的个体， Ｌ ｎｅｗ ｉ 为新产生的个 体，ｎ 为个体的编码长度，１＜ｋ＜ｍ＜ｎ。 ２）方式 ２。 设原个体 Ｌ ＝ （ ｌ １ ，ｌ ２ ，…，ｌ ｎ ），产生的新个体为 ａ ＝ （ａ１ ，ａ２ ，…，ａｎ ），随机数 ｐ ＝ ｒａｎｄ（０，１） （０ 和 １ 之 间的随机小数），则产生新个体方式如下： ａｊ ＝ ｜ ｌ ｊ － １ ｜， ｐ ＞ Ｐｍ ｌ { ｊ， 其他 （５） 式中：Ｐｍ∈［０，１］，新个体 Ｌ ｎｅｗ ｉ ＝ ａ，１＜ｊ＜ｎ。 为了对解空间进行充分的搜索，这 ２ 种方式都 会被使用，在算法运行过程中随机选择其中的一种 方式来产生新个体。 新个体产生后计算适应度 ｆ（Ｌ ｎｅｗ ｉ ） 和新旧个体间的适应度增量△Ｅ ＝ ｆ（Ｌ ｎｅｗ ｉ ） － ｆ（Ｌｉ），并计算 ｐ ＝ ｅｘｐ（ －△Ｅ ／ Ｔ），按概率 ｐ 选用或者 是舍弃新个体，重复上述过程一定次数后选择新搜 索到的适应度高的个体进入下一代。 ２ 混合差分进化算法 混合差分进化算法是差分进化算法和模拟退火 算法的合理组合，首先由一组随机产生的初始解开 始搜索，通过带有精英保留策略的遗传操作产生新 个体，然后对每一个新个体进行独立的模拟退火操 作，将操作完成后生成的个体作为混合算法的下一 代个体，并进行退温操作，经过若干次迭代后，最终 选择种群中最优解作为所求问题的解。 混合差分进 化算法流程如图 １ 所示。 ·１１０· 智 能 系 统 学 报 第 ９ 卷