Benchmarking and Solving Dynamic Constrained Problems

Trung Thanh Nguyen,Xin Yao,Fellow,IEEE

通过读这篇文章的摘要，现实世界的动态约束优化问题在某个时候不仅目标值会变，而且约束也会随着变。现存的动态优化算法难于处理动态数值约束优化问题，作者提出一种新的方法来解决此类问题。并且取得比较的效果，并不是很好的效果说明在这个方面还是存在一定的发展和优化空间，也可以设计更好的方法来进行对比。

处理动态优化问题和动态约束优化问题会是一样的吗？当然不是的。就目前的学术研究来说，用于测试动态约束优化问题的测试函数不够成熟。之所以会出现这种情况的原因应该有很多种，肯定也有很多牛人去尝试过，去设计过，问题太复杂了，或者用处不是很大，阻碍了其发展。这是一种在不确定的环境下设计的。

 一些性质使得动态约束问题更加困难。

 现有的不可行区域可能会使保持多样性的方法不太有效。这一句话确实不是很懂，在处理约束的时候很少提到保持多样性的问题。我还得想想，应该会还有其它的意思。

在不连续可行区域的全局最优解可能会使惩罚函数不太有效。这应该没有错。当多个不连续可行区域存在的时候，这时候罚函数就没有多太的用处。因为在这个时候，全局最优解可能从一个区域跳到另一个区域。而在一般的约束优化问题中，罚函数最常用的，也是最容易实现，但是效果不能说好，也不能说不好。最主要要根据测试函数来判断。

  变化的约束可能使寻找最优解的方法失效。找到的最优可以不是可行区域中，那么使下次搜索失去了有效信息。

  为了能够更好的验证自己算法的有效性，列出一系列的测试函数。通过对这些函数的测试从而肯定自己所作的工作是否有意义。由于是动态测试问题，参数一般设置随着时间的变化而变化。从一点我们可以想到什么呢？遗传算法主要是以运行代数来判断是否终止。想到其他变化而变化量少，但是可以肯定是存在的。是否把这样的函数变形成新的函数对其他方面的测试是否可以起到有效的作用呢，这是下步的工作思想。

  列举两个算法：hyper-Mutation GA(hyperM) and random-Immigrant GA(RIGA)进行评估，以证实提出的假设：在DCOPs中的一些性质会阻碍动态优化算法得到最优解。这个算法都是很早的就提出来的，前者是Gobb H.G.于1990年在他的技术报告中提出来的，后者是Grefenstette J.J.于1992年在他的文章提出来的。这应该是比较经典、权威的算法。但是快二十年了难道没有新的算法，比他们好的算法吗？有，当然有。主要是因为这两个算法都是从标准的遗传算法中发展过来的，很容易分析其中的优势和不足。

创建一个平等的测试环境，尽可能的将所有测试算法的参数设置为一样的值。遗传算法对参数的设置相当敏感，如果在做实验的过程中，比较两个算法，参数设置不同，对实验结果的影响是非常大的，所以在测试中，参数设置为一样的是有必要的。

  算法的性能评价，在此文中提到了两个评价方法：performance plots  and  offline error;这两个评价方法，暂时还没有看懂其意思，也可能是在一般的优化算法中评价比较少的一种，但在动态方面应该很有意思的两种评价方法。不太可能吧，在网上没有找到其意思。我想这就应该找专业字典进行查询呢。

  跟踪可行域可以帮助解决动态约束优化问题吗？非约束动态优化策略中跟踪之前的最优信息，也不能保证得到最好的结果。有必要组合一些新的策略更好的开采DCOP的性质，同时处理约束更加有效。在跟踪可行域时，并不能保证得到很好的结果。所以有必要设计更好的算法，这也就是之前所说的难点。跟踪可行域的一种方法：保持一些可行的个体。在每一代，更新这些个体后，还要保证它们总是有效的。而且在搜索的过程中，这些个体可以适当的修补一些不可行的个体。比如，通过将不可解映射到可行解上。另外，经过一代变化后， 最优解可能出现在移动的区域，也可能出现在新的区域。通过这种方法最终还是有可能跟踪到真实的最优解。这个方法，用起来可能会比较复杂，一不小心跟踪的局部最优解，怎么办，那不是只能收敛到局部最优。在实现此方法的同时，必须考虑清楚，怎样才能保证不收敛到局部最优，而是要达到全局最优。