基于全局优化和局部学习的进化多目标优化算法

发布时间：2018-04-17 07:50

本文选题：多目标优化 + 进化算法　；参考：《西安电子科技大学》2016年博士论文

【摘要】：一直以来,最优化问题都是科学研究和工程实践的难点和热点。根据其所需要优化的目标函数的个数,优化问题可以分为单目标优化问题和多目标优化问题。受生物智能启发的进化算法以种群进化的方式不断逼近最优解,具有全局优化的能力,能有效的解决大部分优化问题。然而,进化算法也存在一些缺陷,如收敛速度较慢,运行时间较长等。特别是对于那些比较复杂的优化问题,进化算法通常需要花费足够长的搜索时间才能获得较为满意的解。结合高效的局部学习策略,提高进化算法求解问题的性能,是一个值得研究的重要方向。针对单目标优化问题,已经存在大量的混合优化算法。本论文的主要研究目的就是将局部学习策略引入到多目标优化算法中,设计更高效的算法,并应用于实际问题。论文的主要成果概括如下：(1)针对进化多目标优化算法存在的收敛速度较慢的缺陷,提出了一种新的基于链式局部搜索的混合多目标优化算法。在该算法中,设计了基于链式规则的局部搜索策略,其中,局部搜索的参数,如步长,成功率等被编码在个体中,因而,这些参数能够在局部搜索执行完后得到保留,进一步提高了局部搜索的效率。在选择个体执行局部搜索时,采用了基于多样性的选择机制,在一定程度上避免了局部搜索带来的多样性损失。此外,设计了计算资源的自适应分配策略用来平衡全局优化和局部学习。对比实验的结果表明,局部搜索的策略的引入能够有效的提高进化多目标优化算法的性能。(2)受博弈论中多臂老虎机选择策略的启发,提出了一种自适应多密母算法用于求解单目标柔性作业车间调度问题。该问题是一个极为复杂的离散组合优化问题,传统的数学规划方法很难得到有效解,而进化算法又很难在一定的时间内获得满意解。因此,越来越多的研究者倾向于使用混合算法。面对众多的局部搜索策略,如何选择出适合当前求解问题的策略是设计算法的一个难点。我们设计的自适应多密母算法提供了一种自适应选择策略,能够在算法运行的不同阶段自动选择搜索算子。具体的,该自适应选择策略利用一个长度有限的滑动窗口记录不同搜索算子当前的搜索效果,然后基于这些效果去指导后续的算子选择。在多个标准测试数据集的对比实验结果表明,相对于现有的代表性算法,该算法能够获得更优的效果。(3)针对传统推荐算法仅仅致力于提高推荐准确率这一目标的不足,提出了一种基于多目标优化的个性化推荐算法。在算法中,物品推荐问题被建模成一个多目标优化问题,优化的两个目标为准确率和多样性。其中,为了度量物品推荐的准确率,使用了概率传播算法,而多样性的度量使用的是覆盖率这一指标。针对建模后的优化问题,设计了合理而有效的个体编码和相应的遗传操作算子。特别的,在设计的个体编码中,多个用户的推荐结果被编码在同一个个体里。因此,通过求解该问题,算法能够在一次运行中给多个用户提供多组推荐。为了提高算法效率,还使用聚类算法将用户划分为相对较小的集合。实验结果验证了算法的有效性。(4)针对标签系统的特性,提出了一种基于深度神经网络的推荐算法。在标签系统中,用户可以用任何词汇去描述或者评价物品,不再拘泥于固有的等级评分机制。然而,这些词汇给可能给标签信息带来困难,如导致标签信息的冗余性或多义性等。如何处理标签信息成为算法设计的难点。基于这个难点,我们通过引入深度神经网络构建了一个新的推荐算法。首先,算法将标签系统中,用户、物品之间三维关系转换为两个二维矩阵,获取每个用户基于标签的信息。接着,利用稀疏自动编码器这一深度网络模型从这些信息中提取出新的特征。相对于初始的特征,这些特征不再稀疏,且更具有代表性。最后,基于这些特征,利用协同过滤算法产生推荐结果。在两个网络数据集的实验结果表明,相对于原始的协同过滤算法和基于聚类的协同过滤算法,该算法在准确率上能取得更优的结果。
[Abstract]:All along, the optimization problems are the hot and difficult scientific research and engineering practice. According to the number of the need to optimize the objective function of the optimization problem can be divided into single objective optimization and multi-objective optimization problem. The evolutionary algorithm inspired by evolutionary biology intelligent way to approach the optimal solution, has the ability of global optimization, can effectively solve the most optimization problems. However, the evolutionary algorithm has some defects, such as slow convergence, long running time. Especially for those complicated optimization problems, evolutionary algorithm usually takes long enough time to search for satisfactory solutions. Combining with local efficient learning strategies and improve the performance of evolutionary algorithm for solving the problem, is an important direction worthy of study. According to a single objective optimization problem, a hybrid optimization algorithm already exists. The main purpose of this thesis is the local learning strategy is introduced into the multi-objective optimization algorithm, design a more efficient algorithm, and applied to practical problems. The main results are summarized as follows: (1) based on evolutionary multi-objective optimization algorithm are slow convergence defects, put forward a new hybrid the target chain optimization algorithm based on local search. In this algorithm, the design of the local search strategy, chain based on rules and parameters, such as the local search step, the success rate is in the encoding of individuals, therefore, these parameters can be retained in the local search after the implementation, to further improve the efficiency of local search in the choice of the individual. Performs a local search, the selection mechanism based on diversity, to a certain extent, to avoid the loss of the diversity of local search brings. In addition, the design of adaptive computing resources Should the allocation strategy to balance the global optimization and local learning. The experimental results show that the introduction of local search strategies can improve the effective evolutionary algorithm for multiobjective optimization performance. (2) by game theory inspired in the multi arm slot machine selection strategy, put forward a kind of adaptive multi Memetic Algorithm for solving the single objective flexible job shop scheduling problem. The problem is an extremely complex discrete combinatorial optimization problems, the traditional mathematical methods are difficult to obtain effective solutions, and the evolutionary algorithm is hard to in a certain period of time to get the satisfactory solution. Therefore, more and more researchers tend to use the hybrid algorithm in the face of local. Many search strategies, how to select suitable for the problem solving strategy is a difficult design algorithm. We design an adaptive multi memetic algorithm provides an adaptive selection strategy in algorithm The different stages of the operation to automatically select the search operator. Specifically, the adaptive selection strategy using a finite length sliding window search effect of different search operator current, then based on these results to guide subsequent operator choice. Comparing the experimental results in a number of standard datasets show that compared with the existing representative algorithm. The algorithm can obtain better results. (3) aiming at shortcomings of traditional recommendation algorithms only committed to improving the recommendation accuracy of this goal, proposes a recommendation algorithm for multi objective optimization based personalized recommendation algorithm. In the article, problem is formulated as a multi-objective optimization problem, the optimization of the two target for accuracy and diversity. Among them, in order to accurately measure items recommended by using the probability propagation algorithm, and the diversity metric used is the coverage of this index for the construction. After the optimization of mold design, reasonable and effective individual encoding and corresponding genetic operators. In particular, in the individual encoding design, multiple user recommendation results are encoding in the same individual. Therefore, by solving the problem, the algorithm can run in a multi group provide recommendation to many users. In order to improve the efficiency of the algorithm, users will also be divided into a relatively small set using clustering algorithm. The experimental results verify the effectiveness of the algorithm. (4) according to the characteristics of the label system, presents a deep neural network recommendation algorithm based on tags. In the system, users can use any words to describe or evaluation items, no longer adhere to the inherent rating mechanism. However, these words can be difficult to label information, such as the resulting label information is redundant or ambiguity. How to deal with the label information is becoming The difficulty method design. Based on this difficulty, we construct a new recommendation algorithm by introducing the depth of the neural network. Firstly, the algorithm user tag system, the relationship between items, conversion of 3D into two dimensional matrix for each user tags based on the information. Then, using the depth encoder automatic sparse network model the extraction of new features from these information. Compared with the initial features, these features are no longer sparse, and more representative. Finally, based on these features, using collaborative filtering algorithm to produce the recommended results. In the two network data sets. The experimental results show that compared with the original collaborative filtering algorithm and collaborative filtering algorithm based on clustering the proposed algorithm can achieve better results in accuracy.

【学位授予单位】：西安电子科技大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP18

【相似文献】