CN108038538A - 基于强化学习的多目标进化算法 - Google Patents
基于强化学习的多目标进化算法 Download PDFInfo
- Publication number
- CN108038538A CN108038538A CN201711279238.2A CN201711279238A CN108038538A CN 108038538 A CN108038538 A CN 108038538A CN 201711279238 A CN201711279238 A CN 201711279238A CN 108038538 A CN108038538 A CN 108038538A
- Authority
- CN
- China
- Prior art keywords
- mrow
- value
- population
- msup
- solution
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N3/00—Computing arrangements based on biological models
- G06N3/004—Artificial life, i.e. computing arrangements simulating life
- G06N3/006—Artificial life, i.e. computing arrangements simulating life based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N3/00—Computing arrangements based on biological models
- G06N3/02—Neural networks
- G06N3/08—Learning methods
- G06N3/086—Learning methods using evolutionary algorithms, e.g. genetic algorithms or genetic programming
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Health & Medical Sciences (AREA)
- Life Sciences & Earth Sciences (AREA)
- General Health & Medical Sciences (AREA)
- General Physics & Mathematics (AREA)
- Computational Linguistics (AREA)
- Data Mining & Analysis (AREA)
- Evolutionary Computation (AREA)
- Biomedical Technology (AREA)
- Molecular Biology (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- Biophysics (AREA)
- Mathematical Physics (AREA)
- Software Systems (AREA)
- Artificial Intelligence (AREA)
- Bioinformatics & Cheminformatics (AREA)
- Bioinformatics & Computational Biology (AREA)
- Evolutionary Biology (AREA)
- Physiology (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
本发明公开了基于强化学习的多目标进化算法，从搜索空间中随机产生初始种群，对所求得的种群进行评价；对不满足终止条件的种群，利用强化学习选择的DEvariant算子和T算子产生新的值，并对其与邻域的值进行交叉，变异产生新解；产生的新解，与原种群的解进行比较，选择使子问题函数满足最优值的解，来更新种群；利用产生的新种群，计算出新的5维观察向量和回报值R，进而更新RL控制器的状态；判断是否满足终止条件，不满足则不断进行迭代计算，直到满足终止条件，结束。本发明有效解决了MOEA/D对于T参数调节不敏感的问题。
Description
技术领域
本发明涉及科学和工程技术领域，尤其涉及基于强化学习的多目标进化算法。
背景技术
在科学和工程领域存在大量的多目标优化问题(Multi-objectiveOptimizationProblem，MOP)，与单目标优化问题(Single-objectiveOptimization Problem，SOP)不同，MOP的最优解是由所谓Pareto最优解组成的集合。传统多目标优化算法包括加权法、约束法、目标规划法和极小极大法等。这些方法都是将MOP转换为SOP，其缺点是需要充分的先验知识，而且难以处理目标噪声，鲁棒性较差。由于多目标优化问题的目标函数和约束函数可能是非线性、不可微或不连续的，传统的数学规划方法往往效率较低，且它们对于权重值或目标给定的次序较敏感。
2.进化算法(EvolutionaryAlgorithm，EA)是一种模拟自然进化过程的随机全局优化方法，EA采用群体搜索和群体中个体间信息交换的方式搜索问题的解。由于EA固有的并行性，有可能在模拟中找到多个Pareto最优解。与传统算法比较，其优点在于：首先，进化搜索过程具有随机性，不易陷入局部最优；其次，EA具有固有的并行性，能够同时进化寻找到多个解，适合多目标优化问题；第三，能够处理不连续，不可微和Pareto前沿非凸等问题，不需要过多先验知识。
3.算法基于Pareto占优机制，采用不同的适应度分配策略和选择机制；采取不同方案保持种群多样性并避免算法过早收敛，使得算法的Pareto解分布均匀。
4.作为一种高效的和具有良好鲁棒性的多目标优化器，由于多目标进化算法的优势，MOEA已经被广泛应用于科学和工程的许多领域，包括控制工程、系统规划、生产调度、数据挖掘等。
5.MOEA/D将MOP分解为N个标量的子问题。它通过进化出一个解的种群来同时解决所有子问题。对于每一代种群，种群是从所有代中选出的每一个子问题的最优解的集合。相邻两个子问题键的关联程度是由它们的聚合系数向量间的距离所决定的。对于两个相邻子问题来说，最优解应该是非常相似的。对于每一个子问题来说，只是用与其相邻的子问题的信息来优化它。
MOEA/D有以下特性：
MOEA/D提供了一个简单但是有效的方法，那就是将分解的方法引入到多目标进化计算中。对于常常在数学规划领域发展的分解方法，它可以真正的被并入到EA中，通过使用MOEA/D框架来解决MOP问题。因为MOEA/D算法是同时优化N标量子问题而不是直接将MOP问题作为一个整体来解决，那么对于传统的并不是基于分解的MOEA算法来说适应度分配和多样性控制的难度将在MOEA/D框架中得到降低。
6.但是，MOEA/D存在着不足，就是对于T参数调节不敏感，T小了没有广度，大了没有深度，自适应调节能力差。
发明内容
本发明的目的在于克服现有技术的缺点，提供基于强化学习的多目标进化算法，以解决上述技术问题。
为实现上述目的本发明采用以下技术方案：
基于强化学习的多目标进化算法，包括如下步骤：步骤1、从搜索空间中随机生成初始种群；
步骤2、对所求得的种群根据评估准则进行评价；
步骤3、更新搜索到的目标函数的最佳值；
步骤4、利用产生的近似解Z*和终止条件进行比较判断，满足就结束；对不满足终止条件的种群，利用强化学习RL控制器选择的DEvariant算子和T算子产生新的值，并对其与邻域的值进行交叉，变异产生新解；
步骤5、产生的新解与原种群的解进行比较，选择使子问题函数满足最优值的解，来更新种群；
步骤6、利用产生的新种群，计算出新的5维观察向量和回报值R，进而更新RL控制器的状态，判断是否满足终止条件，不满足则不断进行迭代计算，直到满足终止条件，结束。
优选的，所述步骤1的具体步骤为：
步骤1.1、计算任意两个权重向量间的欧式距离，查找每个权重向量最近的T个权重向量，其中T是每一个邻域中的权重向量的个数，对于每个i＝1,…,N，令Bi＝{i1,…,iT}，λi 1,…λi T是λi最近的T个权重向量；
步骤1.2、建立一个外部种群EP，用于存储搜索最优解过程中找到的非支配解，初始化EP为空；
步骤1.3、从搜索空间中均匀随机采集生成使目标函数F(X)＝(f1(x),f2(x),…,fi(x))取最优值的解作为初始种群，其中i＝1,2,...,m；X为一组决策向量，x是自变量；
步骤1.4、利用切比雪夫方法，将目标函数F(X)分解成N层子问题：其中，第i个子问题的相邻关系由所有的子问题关于λi点的权重向量来表示，Z*是目前能搜索到的目标函数的最优向量值，也称为近似解,Z*＝min{(f1(x),f2(x),…,fi(x))}。
优选的，所述步骤4中产生的值与其邻域的值进行如下运算，产生新解：步骤4.1选择运算：从B(i)中随机选取两个序号h,k,运用遗传算子由xh和xk产生一个新的值，其中xh是第h个子问题的当前的最优解，和xk是第k个子问题的当前的最优解；把产生的值与其邻域的值进行比较，进行优胜略汰操作，选择适应度高的优秀的值留下来，遗传到下一代；
步骤4.2交叉运算：对种群中的个体进行配对，进行基因的交叉操作，产生新的个体；
步骤4.3变异运算：对基因值进行低概率的变动操作。
优选的，所述步骤6中回报值R由以下公式得出：
本发明的有益效果是：本发明引入了强化学习机制，利用RL控制器不断优化，可以做到参数的自适应；具体为利用强化学习的RL控制器选择的算子，根据最大奖励R和五维观察向量，来产生最优值不断优化种群，直到满足终止条件，有效解决了MOEA/D对于T参数调节不敏感的问题。
附图说明
图1为本发明方法流程示意图。
图2为本发明在测试UF3问题的验证效果图。
图3为本发明在测试UF7问题的验证效果图。
具体实施方式
下面结合附图和具体实施例对本发明作进一步详细阐述。
如图1所示，基于强化学习的多目标进化算法，包括如下步骤：
步骤1、从搜索空间中随机生成初始种群；
步骤1.1、计算任意两个权重向量间的欧式距离，查找每个权重向量最近的T个权重向量，其中T是每一个邻域中的权重向量的个数，对于每个i＝1,…,N，令Bi＝{i1,…,iT}，λi 1,…λi T是λi最近的T个权重向量；
步骤1.2、建立一个外部种群EP，用于存储搜索最优解过程中找到的非支配解，初始化EP为空；
步骤1.3、从搜索空间中均匀随机采集生成使目标函数F(X)＝(f1(x),f2(x),…,fi(x))取最优值的解作为初始种群，其中i＝1,2,...,m；X为一组决策向量，x是自变量；
步骤1.4、利用切比雪夫方法，将目标函数F(X)分解成N层子问题：其中，第i个子问题的相邻关系由所有的子问题关于λi点的权重向量来表示，Z*是目前能搜索到的目标函数的最优向量值，也称为近似解,Z*＝min{(f1(x),f2(x),…,fi(x))}。
步骤2、对所求得的种群根据评估准则进行评价；
步骤3、更新搜索到的目标函数的最佳值；
步骤4、利用产生的近似解Z*和终止条件进行比较判断，满足就结束；对不满足终止条件的种群，利用强化学习RL控制器选择的DEvariant算子和T算子产生新的值，并对其与邻域的值进行交叉，变异产生新解；
产生的值与其邻域的值进行如下运算，产生新解：
步骤4.1选择运算：从B(i)中随机选取两个序号h,k,运用遗传算子由xh和xk产生一个新的值，其中xh是第h个子问题的当前的最优解，和xk是第k个子问题的当前的最优解；把产生的值与其邻域的值进行比较，进行优胜略汰操作，选择适应度高的优秀的值留下来，遗传到下一代；
步骤4.2交叉运算：对种群中的个体进行配对，进行基因的交叉操作，产生新的个体；
步骤4.3变异运算：对基因值进行低概率的变动操作。
步骤5、产生的新解与原种群的解进行比较，选择使子问题函数满足最优值的解，来更新种群；
步骤6、利用产生的新种群，计算出新的5维观察向量和回报值R，进而更新RL控制器的状态，判断是否满足终止条件，不满足则不断进行迭代计算，直到满足终止条件，结束。
回报值R由以下公式得出：
如图2-3所示，为了表明算法的有效性，选取了两个标准测试集UF3，UF7来验证。其中UF3，UF7为2个目标的优化问题。群体规模设为300。实验结果表明，基于强化学习的多目标优化算法在对T参数的调节上优于的MOEA/D算法。
本发明引入了强化学习机制，利用RL控制器不断优化，可以做到参数的自适应；利用强化学习的RL控制器选择的算子，根据最大奖励R和五维观察向量，来产生最优值不断优化种群，直到满足终止条件，有效解决了MOEA/D对于T参数调节不敏感的问题。
以上所述为本发明较佳实施例，对于本领域的普通技术人员而言，根据本发明的教导，在不脱离本发明的原理与精神的情况下，对实施方式所进行的改变、修改、替换和变型仍落入本发明的保护范围之内。
Claims (4)
1.基于强化学习的多目标进化算法，其特征在于，包括如下步骤：
步骤1、从搜索空间中随机生成初始种群；
步骤2、对所求得的种群根据评估准则进行评价；
步骤3、更新搜索到的目标函数的最佳值；
步骤4、利用产生的近似解Z*和终止条件进行比较判断，满足就结束；对不满足终止条件的种群，利用强化学习RL控制器选择的DEvariant算子和T算子产生新的值，并对其与邻域的值进行交叉，变异产生新解；
步骤5、产生的新解与原种群的解进行比较，选择使子问题函数满足最优值的解，来更新种群；
步骤6、利用产生的新种群，计算出新的5维观察向量和回报值R，进而更新RL控制器的状态，判断是否满足终止条件，不满足则不断进行迭代计算，直到满足终止条件，结束。
2.根据权利要求1所述的基于强化学习的多目标进化算法，其特征在于，所述步骤1的具体步骤为：
步骤1.1、计算任意两个权重向量间的欧式距离，查找每个权重向量最近的T个权重向量，其中T是每一个邻域中的权重向量的个数，对于每个i＝1,…,N，令Bi＝{i1,…,iT}，λi 1,…λi T是λi最近的T个权重向量；
步骤1.2、建立一个外部种群EP，用于存储搜索最优解过程中找到的非支配解，初始化EP为空；
步骤1.3、从搜索空间中均匀随机采集生成使目标函数F(X)＝(f1(x),f2(x),…,fi(x))取最优值的解作为初始种群，其中i＝1,2,...,m；X为一组决策向量，x是自变量；
步骤1.4、利用切比雪夫方法，将目标函数F(X)分解成N层子问题：其中，第i个子问题的相邻关系由所有的子问题关于λi点的权重向量来表示，Z*是目前能搜索到的目标函数的最优向量值，也称为近似解,Z*＝min{(f1(x),f2(x),…,fi(x))}。
3.根据权利要求2所述的基于强化学习的多目标进化算法，其特征在于，所述步骤4中产生的值与其邻域的值进行如下运算，产生新解：步骤4.1选择运算：从B(i)中随机选取两个序号h,k,运用遗传算子由xh和xk产生一个新的值，其中xh是第h个子问题的当前的最优解，和xk是第k个子问题的当前的最优解；把产生的值与其邻域的值进行比较，进行优胜略汰操作，选择适应度高的优秀的值留下来，遗传到下一代；
步骤4.2交叉运算：对种群中的个体进行配对，进行基因的交叉操作，产生新的个体；
步骤4.3变异运算：对基因值进行低概率的变动操作。
4.根据权利要求3所述的基于强化学习的多目标进化算法，其特征在于，所述步骤6中回报值R由以下公式得出：
<mrow>
<mi>R</mi>
<mo>=</mo>
<munderover>
<mo>&Sigma;</mo>
<mrow>
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mi>N</mi>
</munderover>
<mfrac>
<mrow>
<msup>
<mi>g</mi>
<mrow>
<mi>t</mi>
<mi>e</mi>
</mrow>
</msup>
<mrow>
<mo>(</mo>
<msubsup>
<mi>X</mi>
<mrow>
<mi>t</mi>
<mo>-</mo>
<mn>1</mn>
</mrow>
<mi>i</mi>
</msubsup>
<mo>|</mo>
<msup>
<mi>&lambda;</mi>
<mi>i</mi>
</msup>
<mo>,</mo>
<mi>z</mi>
<mo>*</mo>
<mo>)</mo>
</mrow>
<mo>-</mo>
<msup>
<mi>g</mi>
<mrow>
<mi>e</mi>
<mi>t</mi>
</mrow>
</msup>
<mrow>
<mo>(</mo>
<msubsup>
<mi>X</mi>
<mi>t</mi>
<mi>i</mi>
</msubsup>
<mo>|</mo>
<msup>
<mi>&lambda;</mi>
<mi>i</mi>
</msup>
<mo>,</mo>
<mi>z</mi>
<mo>*</mo>
<mo>)</mo>
</mrow>
</mrow>
<mrow>
<msup>
<mi>g</mi>
<mrow>
<mi>t</mi>
<mi>e</mi>
</mrow>
</msup>
<mrow>
<mo>(</mo>
<msubsup>
<mi>X</mi>
<mrow>
<mi>t</mi>
<mo>-</mo>
<mn>1</mn>
</mrow>
<mi>i</mi>
</msubsup>
<mo>|</mo>
<msup>
<mi>&lambda;</mi>
<mi>i</mi>
</msup>
<mo>,</mo>
<mi>z</mi>
<mo>*</mo>
<mo>)</mo>
</mrow>
</mrow>
</mfrac>
<mo>.</mo>
</mrow>
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201711279238.2A CN108038538A (zh) | 2017-12-06 | 2017-12-06 | 基于强化学习的多目标进化算法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201711279238.2A CN108038538A (zh) | 2017-12-06 | 2017-12-06 | 基于强化学习的多目标进化算法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN108038538A true CN108038538A (zh) | 2018-05-15 |
Family
ID=62095661
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201711279238.2A Pending CN108038538A (zh) | 2017-12-06 | 2017-12-06 | 基于强化学习的多目标进化算法 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN108038538A (zh) |
Cited By (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108805268A (zh) * | 2018-06-08 | 2018-11-13 | 中国科学技术大学 | 基于进化算法的深度强化学习策略网络训练方法 |
| CN108830370A (zh) * | 2018-05-24 | 2018-11-16 | 东北大学 | 基于增强学习型菌群觅食算法的特征选择方法 |
| CN110174118A (zh) * | 2019-05-29 | 2019-08-27 | 北京洛必德科技有限公司 | 基于强化学习的机器人多目标搜索路径规划方法和装置 |
| CN110704959A (zh) * | 2019-08-19 | 2020-01-17 | 南昌航空大学 | 基于迁移行为的moead优化夹具布局的方法及装置 |
| CN110782016A (zh) * | 2019-10-25 | 2020-02-11 | 北京百度网讯科技有限公司 | 用于优化神经网络架构搜索的方法和装置 |
| CN111045325A (zh) * | 2018-10-11 | 2020-04-21 | 富士通株式会社 | 优化装置及优化装置的控制方法 |
| TWI741760B (zh) * | 2020-08-27 | 2021-10-01 | 財團法人工業技術研究院 | 學習式生產資源配置方法、學習式生產資源配置系統與使用者介面 |
-
2017
- 2017-12-06 CN CN201711279238.2A patent/CN108038538A/zh active Pending
Cited By (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108830370A (zh) * | 2018-05-24 | 2018-11-16 | 东北大学 | 基于增强学习型菌群觅食算法的特征选择方法 |
| CN108830370B (zh) * | 2018-05-24 | 2020-11-10 | 东北大学 | 基于增强学习型菌群觅食算法的特征选择方法 |
| CN108805268A (zh) * | 2018-06-08 | 2018-11-13 | 中国科学技术大学 | 基于进化算法的深度强化学习策略网络训练方法 |
| CN111045325A (zh) * | 2018-10-11 | 2020-04-21 | 富士通株式会社 | 优化装置及优化装置的控制方法 |
| CN110174118A (zh) * | 2019-05-29 | 2019-08-27 | 北京洛必德科技有限公司 | 基于强化学习的机器人多目标搜索路径规划方法和装置 |
| CN110704959A (zh) * | 2019-08-19 | 2020-01-17 | 南昌航空大学 | 基于迁移行为的moead优化夹具布局的方法及装置 |
| CN110704959B (zh) * | 2019-08-19 | 2022-04-08 | 南昌航空大学 | 基于迁移行为的moead优化夹具布局的方法及装置 |
| CN110782016A (zh) * | 2019-10-25 | 2020-02-11 | 北京百度网讯科技有限公司 | 用于优化神经网络架构搜索的方法和装置 |
| TWI741760B (zh) * | 2020-08-27 | 2021-10-01 | 財團法人工業技術研究院 | 學習式生產資源配置方法、學習式生產資源配置系統與使用者介面 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN108038538A (zh) | 基于强化学习的多目标进化算法 | |
| Chen et al. | I-Ching divination evolutionary algorithm and its convergence analysis | |
| Shang et al. | Community detection based on modularity and an improved genetic algorithm | |
| CN110363344A (zh) | 基于miv-gp算法优化bp神经网络的概率积分参数预测方法 | |
| CN109932903A (zh) | 多父代优化网络和遗传算法的风机控制多目标优化方法 | |
| Zhang et al. | A convolutional neural network-based surrogate model for multi-objective optimization evolutionary algorithm based on decomposition | |
| CN107067121A (zh) | 一种基于多目标的改进灰狼优化算法 | |
| Liu et al. | A dynamic multi-objective optimization model with interactivity and uncertainty for real-time reservoir flood control operation | |
| Sato et al. | Variable space diversity, crossover and mutation in MOEA solving many-objective knapsack problems | |
| CN104616062B (zh) | 一种基于多目标遗传规划的非线性系统辨识方法 | |
| Garcia-Lopez et al. | An improved robust topology optimization approach using multiobjective evolutionary algorithms | |
| CN109858798B (zh) | 关联改造措施与电压指标的电网投资决策建模方法及装置 | |
| Kordík et al. | Meta-learning approach to neural network optimization | |
| Li et al. | A novel adaptive weight algorithm based on decomposition and two-part update strategy for many-objective optimization | |
| Jadav et al. | Optimizing weights of artificial neural networks using genetic algorithms | |
| CN110009181A (zh) | 配电网改造措施与失负荷量指标关联性挖掘方法及装置 | |
| Korejo et al. | Multi-population methods with adaptive mutation for multi-modal optimization problems | |
| CN105512755A (zh) | 一种基于分解的多目标分布估计优化方法 | |
| CN104732067A (zh) | 一种面向流程对象的工业过程建模预测方法 | |
| Zheng et al. | Data-driven optimization based on random forest surrogate | |
| Zhang et al. | Embedding multi-attribute decision making into evolutionary optimization to solve the many-objective combinatorial optimization problems | |
| Guo et al. | Hybridizing cellular automata principles and NSGAII for multi-objective design of urban water networks | |
| CN105426959A (zh) | 基于bp神经网络与自适应mbfo算法的铝电解节能减排方法 | |
| CN115310654A (zh) | 基于强化学习-非支配排序遗传算法的作业车间调度方法 | |
| CN106022464A (zh) | 一种基于聚类的高维多目标进化方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| RJ01 | Rejection of invention patent application after publication | ||
| RJ01 | Rejection of invention patent application after publication |
Application publication date: 20180515 |