65.9K
CodeProject 正在变化。 阅读更多。
Home

TridentOpt：多目标优化引擎或求解器

trident99
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.92/5 (17投票s)

2017年11月7日

MIT

13分钟阅读

viewsIcon

39064

downloadIcon

1295

描述了一种使用混合遗传算法 - 多智能体系统的新型开源通用多目标优化引擎

作者：Anthony Daniels

摘要

本文描述了一个新的通用多目标优化引擎，该引擎使用混合遗传算法-多智能体系统。与传统的多目标方法不同，所提出的方法将问题转化为模糊规划的等价形式，包括模糊目标和约束。然后，该方法对目标函数和约束执行模糊集运算，将信息合并成一个单一的目标和一个单一的约束。然后，使用这个单一的目标和单一的约束来对模糊帕累托集进行排序并剔除劣质解。

索引词—多目标优化、遗传算法、多智能体系统、模糊规划、开源、优化求解器

I 引言

近年来，混合进化算法得到了大量的开发。混合遗传算法-多智能体系统（HGA-MAS）[1][2][10]的引入证明，通过引入代表个体变量利益的多个智能体，可以极大地加速遗传算法的收敛速度。与传统的遗传算法[1]相比，收敛速度快了几个数量级（所有参考文献请参阅附带的技术论文）。原因是多智能体系统为遗传算法的个体染色体提供了局部爬山能力。

II HGA-MAS框架

在所提出的HGA-MAS中，种群包含一组染色体（或候选设计）。值得注意的是，染色体是实值编码而非二进制。每个染色体都有自己的模型评估器，该评估器能够根据其目标函数和约束来分析染色体。通过拥有自己的模型评估器，这直接支持了优化内核中的多线程并行。每个染色体还拥有一组设计智能体，这些智能体代表构成染色体设计描述的每个变量的利益。所提出的系统遵循图1的示意图。

图1：HGA-MAS示意图

在HGA-MAS的每一代中，求解器执行以下操作

  • 执行设计智能体改进重复N次（用户设置）
  • 执行遗传算法操作（交叉、变异）
  • 将种群注入帕累托集
  • 重新归一化和评估帕累托集和种群
  • 修剪帕累托集

设计智能体改进会话允许每个设计智能体根据自己的利益来改进候选设计。它们向模型评估器提交设计更改请求，模型评估器则接受或拒绝这些更改。每个设计智能体都有机会改进设计，并且此过程重复N次，以便设计智能体在进行破坏性的遗传算法操作之前有时间来改进候选设计。对于遗传算法阶段，应该注意的是，具有最高目标函数值的染色体得到了精英保护（后续章节将对此进行更详细的讨论）。执行一定数量的交叉（尾部交换）和变异操作。操作的数量是种群大小的函数。然后，对当前染色体和活动帕累托集进行重新归一化和评估，并在修剪阶段剔除劣质设计。

III 文献综述

本节将从所提出的系统的角度讨论多目标优化（MOO）的当前状态。在MOO中，科学家试图在满足约束的条件下，选择一个或一组优化有时是冲突的目标函数的解。在这些情况下，通常不是只有一个解，而是一组同样好的解，这些解分布在所谓的帕累托前沿上。有时（但不总是）存在一个帕累托最优解，它在帕累托前沿上提供了输入变量的最佳平衡。典型MOO的数学定义如（1）所示。

在处理多个目标函数时，已经采用了多种方法。其中一种方法称为加权和法或标量化。在这种方法中，每个fi(x)乘以一个标量值?i，并将单个目标函数直接加总成一个长目标函数[8]。所提出的方法具有减少待处理方程数量的类似目标，但作者使用模糊集来实现这一点。另一个相关的研究领域是遗传算法候选解（设计）的非支配排序[9]。该方法侧重于提供一个鲁棒的、广泛且均匀分布的帕累托前沿，并根据目标函数对候选解进行成对排序。这种成对排序将解分类为支配、非支配或劣质。然后，科学家选择最适合他们需求的解。所提出的方法反而利用模糊排序来排列解。

在模糊规划领域，已经有一些努力将目标函数和/或约束转换为模糊效用偏好函数[3][11][12][15]。这些努力已经实现了将多个目标作为集合[3]实现，或作为产生偏好曲面的独立模糊函数[15]实现。这两种方法都有其优点，即减少数据（集合）和提供软计算目标（曲面）。对于本研究的目的，作者选择遵循Buckley[3]的路径，但本研究中进行的模糊集运算略有不同，将在下一节详细介绍。

IV 模糊规划

模糊规划作为一种优化方法，将现有的目标和约束的数学公式转化为模糊偏好函数[3]。这最好通过示例来说明。举例来说，考虑X1 <= 5这个简单的约束。转化后，该约束看起来像图2中的模糊效用偏好函数。小于或等于5时，模糊约束完全满足，效用为1.0。随着约束的违反，效用会降低，直到保持0.05的不满意值。在模糊效用中，完全不满足的约束是一个非零的小数。原因是0效用表示完全不可行。不幸的是，完全不可行值与集合运算在乘法集合推理中会丢失所有信息，从而导致智能体的决策引擎在改进暂时处于搜索空间不可行区域的解决方案方面效率低下。

图2：模糊约束示例—小于或等于

与约束类似，目标函数也可以转化为模糊效用函数。这是通过一个过程完成的，该过程将帕累托集当前的下界和上界转换为线性的模糊效用偏好函数。这同样最好通过示例来说明。假设我们有目标函数max f(x) = x1 + x2^2，并且当前候选解的帕累托集的目标函数值范围为[4.3…15.7]，那么模糊效用将如图3所示。需要注意的是，每一代，单个目标函数的范围都会改变，这就是为什么在每一代的结束时，会根据当前范围对效用函数进行重新归一化，并重新对帕累托集进行排序。

图3：模糊目标函数示例—最大化F(x)

通过对模糊化目标函数执行集合运算，可以将其扩展到多目标优化。例如

Fi(x)是fi(x)的模糊效用函数，MIN是最小集合算子。我们正在最大化模糊效用函数中的最小值。在模糊集数学中，这与AND算子相同。所提出的系统对模糊目标函数集合执行MIN和AVG算子。这与使用标量因子进行加总而非集合运算来组合和减少目标函数数量的加权和多目标方法不同[8]。

使用（4）中的集合算子可以向上施压于目标效用的最小值和平均值。这在存在不满意目标函数（从未满足）的情况下非常有用。平均算子会对整个群体施加压力。同样，相同的算子应用于约束集，将集合卷成一个单一的约束效用。每代对帕累托集进行一次的重新归一化步骤是一项关键操作，因为它提供了候选解及其相互比较的最新图景。模糊排序的目的是提供候选解的相对适应度，而不是某个绝对值。这与传统遗传算法的非支配排序[9]在方法上有所不同。

V 示例问题

为了举例说明，以下问题的目标函数数量限制为两个，以便可以绘制传统的帕累托前沿并与模糊帕累托集进行比较。该示例问题有两个变量、两个目标函数和一个非凸帕累托前沿[16]。优化如下

尽管搜索空间是非凸的，HGA-MAS还是找到了帕累托最优解。图4显示了根据目标函数效用进行颜色映射的帕累托集。当从帕累托最优解移出时，等效用带状清晰可见。

图4：示例问题帕累托前沿模糊效用

图5：示例问题前十大设计

VII 理论部分结论

混合遗传算法-多智能体系统与模糊规划的结合，产生了一个可以简化多目标优化的求解器。通过将传统优化问题转化为模糊规划形式，科学家可以通过集合运算将目标函数和约束减少到每个元素。这极大地简化了问题的实际优化。此外，还可以轻松地混合最小化、最大化和目标寻求目标函数。在每个示例问题中，求解器都能在100代内找到帕累托最优解。这包括凸形和非凸形问题。这种类型的求解器在处理整数规划问题（如箱子打包[2]）方面也取得了成功。

VIII TridentOpt 代码手册

既然已经讨论了TridentOpt的工作原理，有必要详细讨论代码库。GUI是用QT 5.8编写的，所以您需要安装它的开源版本。还应该提到，TridentOptCore从序列化到随机数生成，大量使用了HPC模板库。

对象层次结构的顶层是TOptPopulation。TOptPopulation有两个TOptChromosomes集合，即候选设计的活动种群和帕累托集。每个TOptChromosome都包含定义正在解决问题的必要信息。TOptChromosome包含一个TOptObjective集合、一个TOptConstraint集合、一个TOptAgent集合和一个TOptModel。求解器的每一代，TOptPopulation都经历以下步骤

void TOptPopulation::ImprovePopulation(void)
       {
              int numChromo, numPareto;
              numChromo = m_arrChromosomes.size();
              //Update the Utility of the population
              this->UpdatePopulationUtilities();
              this->UpdateTopTenElite();
              //Design agents first
              for (int m = 0; ((m < m_intNumDesignCycle) && (m_blnIsRunning == true)); m++)
              {
                     if (m_blnMultiThreaded)
                     {
                           this->ImproveDesignAgentsMT();
                     }
                     else
                     {
                           this->ImproveDesignAgentsST();
                     }
             }

              //Genetic Algorithm Operations Second
              this->ImproveGeneticAlgorithm();
              //Update the Utility of the population
              this->UpdatePopulationUtilities();
              this->UpdateTopTenElite();
              //

              //put the current population in the pareto front for grooming
              for (int m = 0; m < numChromo; m++)
              {
                     numPareto = m_arrParetoSet.size();
                     TOptChromosome * ptrCurr = m_arrChromosomes.at(m);
                     bool blnAlreadyThere = false;
                     for (int n = 0; n < numPareto; n++)
                     {
                           TOptChromosome * ptrParetoCurr = m_arrParetoSet.at(n);
                           m_sngEpsilon = 0.001f;
                           bool blnTest = ptrParetoCurr->IsChromoEqual(ptrCurr, m_sngEpsilon);
                           if (blnTest == true)
                           {
                                  blnAlreadyThere = true;
                                  break;
                           }
                     }

                     if (blnAlreadyThere == false)
                     {//then chromosome not already in pareto.
                           //put it in the pareto for sorting
                           TOptChromosome * ptrNew = new TOptChromosome();
                           *ptrNew = *ptrCurr;
                           ptrNew->Set_ptrEvaluator(m_ptrPopEvaluator);
                           ptrNew->Set_ptrParent(this);
                           m_arrParetoSet.push_back(ptrNew);
                     }
              }//end loop through population

              //now that we have put new solutions in groom the front for bad solutions
              this->GroomParetoFront(false);
              this->SaveParetoSetDump();
              //now sort the population
              std::sort(m_arrChromosomes.m_vect.begin(), m_arrChromosomes.m_vect.end(), 
                 SortChromosomeDescending);
              //this->SortChromosomes(&m_arrChromosomes);
              //randomize the worst
              if (numChromo >= 10)
              {
                     int intReseed = round(numChromo * 0.1f);
                     for (int k = numChromo - 1; k >= numChromo - 1 - intReseed; k--)
                     {
                           if ((k >= 0) && (k < numChromo))
                           {
                                   if (m_arrChromosomes.at(k)->Get_blnEliteChromosome() == false)
                                  {
                                         m_arrChromosomes.at(k)->RandomizeChromosome();
                                  }
                                  else
                                  {
                                         int z = 10;//should never get here
                                  }
                           }
                     }
              }
              else
              {
                     //population not big enough, just reseed the last one
                     m_arrChromosomes.at(numChromo - 1)->RandomizeChromosome();
              }
              return;
       }

为了向求解器引入新问题，用户需要编写一个新的TOptModel子类。代码库在文档文件夹中提供了许多示例模型，包括技术论文中的所有模型。为了成功地子类化TOptModel，只需覆盖下面列出的虚拟函数

       class HTL_DLLAPI TOptSineCos : public TOptModel
       {
       public:
              //!Default Constructor
      TOptSineCos();
              //!Destructor
              virtual ~TOptSineCos();
              //!Copy Constructor
      TOptSineCos(const TOptSineCos& rhs);
              //PUBLIC OPERATOR OVERLOADS
      TOptSineCos & operator = (const TOptSineCos & rhs);

       public:
              //!Construct the design Chromosome from which all copies will be made
              virtual int CreateDesignChromosome(void);
     
       protected:
      
              //Performs the actual calculation of the objective functions and
              virtual int CalculateModel(void);

      const double m_PI = 3.14159265359f;
       };//end class

CreateDesignChromosome函数构建设计染色体。这是TOptPopulation中所有其他染色体将被复制的TOptChromosome。您必须为问题设置TOptObjectives、TOptConstraints和TOptAgents（变量）。智能体有两种模式：单步模式和梯度模式。单步模式在任一方向上迈出一小步，而梯度模式则沿着导数方向迈出多步，直到找到局部最优解。使用提供的代码示例来成功实现。CalculateModel是您实际计算优化问题的数学模型的地方。这是TOptModel的核心。让我们看看TOptSineCos模型函数。

   double phi1(double s1, double s2)
   {
      return ((1.0 / 2.0) * sin(s1)) - (2 * cos(s1)) + sin(s2) - ((3.0 / 2.0) * cos(s2));
   }
   double phi2(double s1, double s2)
   {
      return ((3.0 / 2.0) * sin(s1)) - (cos(s1)) + (2.0*sin(s2)) - ((1.0 / 2.0) * cos(s2));
   }

      int TOptSineCos::CalculateModel()
      {
      double s1, s2, J1, J2;

      //get the inputs
      s1 = m_arrVars.at(0);
      s2 = m_arrVars.at(1);
      //perform the calculations
      J1 = 1.0f + pow(phi1(1.0, 2.0) - phi1(s1, s2), 2) + pow(phi2(1.0, 2.0) - phi2(s1, s2), 2);
      J2 = pow(s1 + 3.0, 2) + pow(s2 + 1.0, 2);
      //now copy back to the arrays
      m_arrObjs.at(0) =  J1;//F1
      m_arrObjs.at(1) = J2;//F2

      //resize the constraints
      m_arrConsts.at(0) = s1;//X1 <= 10
      m_arrConsts.at(1) = s1;//X1 >= 0
      m_arrConsts.at(2) = s2;//X2 <= 20
      m_arrConsts.at(3) = s2;//X2 >= 0
      return 1;
      }

读者会注意到，数学是前面示例问题中提到的方程5中概述的方程。流程很简单。导入变量，计算目标和约束，并将这些值返回给容器。m_arrVars是变量的容器，m_arrObjs是目标的容器，m_arrConsts是约束值的容器。只要满足这些输入和输出，TridentOpt引擎就会处理其余的细节。

还有一个细节。为了让模型加载到系统中，它必须注册到TOptModelFactory。这通过头文件中的以下语句完成。

//OBJECT FACTORY REGISTRATION CODE
static bool blnTOptSineCos_Registered = 
HTL::GetBaseFactoryPtr()->Register<TOptSineCos>("TOptSineCos");

static bool blnTOptSineCos_Registered2 = 
TridentOptCore::GetModelFactoryPtr()->Register<TOptSineCos>("TOptSineCos");

参考文献

[1] Daniels A. and M. G. Parsons, “An agent based approach to space allocation in general arrangements”, Proceedings of the 9th International Marine Design Conference, Ann Arbor, MI, May 2006.

[2] Daniels A. and M.G. Parsons, “Development of a Hybrid Agent – Genetic Algorithm Approach to General Arrangements”, Proceedings of COMPIT 2007, Cortona, Italy, April 2007.  Accepted Journal of Ship Technology Research, 2008.

[3] Buckley J.J., “Fuzzy Programming and the Pareto Optimal Set”, Fuzzy Sets and Systems, Volume 10, page 57-63. 1983.

[4] Unknown Author, modeFrontier, Inc. “A simple multi-objective optimization problem”,

http://www.math.unipd.it/~marcuzzi/DIDATTICA/LEZ&ESE_PIAI_Matematica/3_cones.pdf

有关更多信息，请访问：www.esteco.com或发送电子邮件至：modeFRONTIER@esteco.com

[5]Unkown Author, “Solving Three-objective Optimization Problems Using Evolutionary Dynamic Weighted Aggregation: Results and Analysis”,  Department of Computing, University of Surrey, Guildford, Surrey, GU2 7XH, UK

www.soft-computing.de/moo3D.pdf

[6] R. Viennet, C Fonteix, and I. Marc. “Multi-criteria optimization using genetic algorithms for determining a pareto set”, International Journal of Systems Science, Volume 27(2), page 255-260, 1996.

[7] Zhenan He, Gary G. Yen, and Jun Zhang, “Fuzzy-Based Pareto Optimality for Many-Objective Evolutionary Algorithms” IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, Volume 18, NO. 2, April 2014

[8] Santos Silva Carlos A. “Multi-objective Optimization Overview”, MIT Portugal

https://fenix.tecnico.ulisboa.pt/downloadFile/3779575589383/Class8

[9] Fonseca Carlos M. and Peter J. Fleming “Genetic Algorithms for Multi-objective Optimization: Formulation, Discussion and Generalization”,  Genetic Algorithms: Proceedings of the Fifth International Conference (S. Forrest, ed.), San Mateo, CA: Morgan Kaufmann, July 1993.

[10] Adnan Acan , “GAACO: A GA + ACO Hybrid for Faster and Better Search Capability”, International Workshop on Ant Algorithms, pages 300-301. ANTS 2002

[11] Koppen Mario, Raul Vicente-Garcia, and Bertram Nickolay “Fuzzy-Pareto-Dominance and its Application in Evolutionary Multi-Objective Optimization”, Third International Conference, EMO 2005, Guanajuato, Mexico, March 9-11, 2005. Proceedings.

[12] Erfani Tohid and Sergei V.Utyuzhnikov, “Handling Uncertainty and Finding Robust Pareto Frontier in Multi-objective Optimization Using Fuzzy Set Theory”, 51st AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference Orlando, Florida. April 2010.

[13] Chase N., M. Rademacher, E. Goodman “A Benchmark Study of Multi-Objective Optimization Methods”

https://www.researchgate.net/publication/242077047_A_Benchmark_Study_of_Multi-Objective_Optimization_Methods

[14] Deb Kalyanmoy, Samir Agrawal, Amrit Pratap, and T Meyarivan, “A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II”, International Conference on Parallel Problem Solving from Nature, PPSN 2000: Parallel Problem Solving from Nature PPSN VI pp 849-858.

[15] Ghosh Debdas, Debjani Chakraborty “A method to obtain fuzzy Pareto set of fuzzy multi-criteria quadratic programming problems”, Annals of Fuzzy Mathematics and Informatics, 2013.

[16] Lopeza RafaelH.,T.G.Rittob,RubensSampaioc and Jose Eduardo S. de Cursid, “A New Multi-Objective Optimization Algorithm For Non-Convex Pareto Fronts and Objective Functions”, Mecánica Computacional Vol XXXII, pages 669-679, Mendoza, Argentina, 19-22 November 2013.

 

© . All rights reserved.