用带蚁群搜索的多种群遗传算法求解作业车间调度问题

结合遗传算法和蚁群算法的优点，提出一种带蚁群搜索的多种群遗传算法．多个种群各自遗传进化，用蚁群搜索得到的解替代各种群中的较劣个体，增加种群的多样性，提高种群的质量；根据各种群最优个体设定初始信息素，大大缩短信息素的累积过程，加快蚁群搜索的速度．利用算法对典型作业车间调度问题进行求解,仿真计算结果表明,该算法是有效的.     

一种多策略结合的改进文化算法

为了更有效地抑制文化遗传算法的早熟收敛现象和提高收敛速度,提出了一种多策略结合的文化遗传算法。该算法在信念空间,使用与文化算法不同的接受函数、影响函数和更新函数,在群体空间,针对种群采取多种群化,并采用自适应的交叉变异操作且多种群之间加入竞争机制的遗传算法,这样使得改进后的算法具有更强的全局寻优能力和局部寻优能力,有效避免陷入局部最优,抑制了早熟收敛,提高了收敛效率。用上述算法对几个典型函数进行优化,实验证明了多种群自适应的文化遗传算法的有效性和可行性,新的算法不易陷入早熟收敛,此外全局搜索能力和局部搜索能力得到有效平衡,收敛率高。     

基于记忆库拉马克进化算法的作业车间调度

多种群遗传算法相比遗传算法在性能上能够有所提高,但对具有较多局部最优解的作业车间调度问题,多种群遗传算法仍然难以改善易陷入局部最优解和局部搜索能力差的缺点.因此,提出了一种求解作业车间调度问题的新算法MGA-MBL(multi-population genetic algorithm based on memory-base and Lamarckian evolution for job shop scheduling problem).MGA-MBL在多种群遗传算法的基础上通过引入记忆库策略,不但使子种群间的个体可以进行信息交换,而且有利于保持整个种群的多样性;通过构造基于拉马克进化机制的局部搜索算子来提高多种群遗传算法中子种群进化的局部搜索能力.由于MGA-MBL采用了全局寻优能力较强的模拟退火算法对记忆库中的个体进行优化,从而缓解了多种群遗传算法易陷入局部最优解的问题,并提高了算法求解作业车间调度问题的性能.对著名的benchmark数据进行测试,实验结果证实了MGA-MBL在求解作业车间调度问题上的有效性.     

基于个体相似度的双种群遗传算法

针对标准遗传算法搜索精度低、容易陷入局部最优解的缺陷,提出一种基于个体相似度的双种群遗传算法。将竞争算子和第二个种群引入标准遗传算法中,在主种群内部利用海明距离计算个体之间的相似度,进行种群内部竞争,保留"种子"个体,而与其相似的个体参与种群之间的交流,从而保持种群多样性。使用经典测试函数对该算法进行了仿真实验,结果表明,该算法能有效抑制"早熟"现象,其全局搜索能力和搜索效果都有了明显的提高。     

自适应分区多代理模型交互式遗传算法

为提高交互式遗传算法的性能.提出一种自适应分区多代理模型交互式遗传算法.该算法基于关键维分割进化初期的搜索空间,同时基于进化进程、逼近精度以及用户评价敏感度,自适应地分割进化中后期的搜索空间.在子空间上,采用多类代理模型学习用户对进化个体评价,并用于评价后续进化的部分或全部个体.将该算法应用于服装进化设计系统,实验结果表明,算法在种群多样性、减轻用户疲劳及用户对优化结果满意度等方面均具有优越性.     

多交叉混沌选择反向小生境遗传算法

为提高小生境遗传算法的全局以及局部搜索能力,提出一种多交叉混沌选择反向小生境遗传算法。利用分段线性混沌映射函数生成一组混沌数序列,在每次进行交叉操作前,依据序列中对应元素的数值大小选择不同的交叉算子进行操作,通过小生境遗传算法产生较优的子代种群。针对子代种群,应用反向搜索策略获得反向种群,在子代种群和反向种群中进行精英选择得到最终新种群,以进一步加强算法的局部寻优能力。仿真实验结果表明,该算法在最优解及均值方面好于小生境遗传算法,从而证明其可行性和优越性。     

基于数论佳点集的遗传算法初始种群均匀设计

文章利用数论中的佳点集理论和方法,给出了遗传算法初始种群生成的一种具有良好多样性的均匀分布设计.通过对遗传算法机理的研究,发现初始种群的分布状态不仅直接关系到遗传算法的全局收敛性,还影响算法的搜索效率,所以对初始种群进行科学合理设定是应用遗传算法进行寻优计算的一个重要问题.基于优化设计思想,提出应用佳点集均匀设计方法确定遗传算法的初始种群.这种方法具有简单易行、种群多样性好、更适合多维情况等特点,实验结果验证了该方法可以有效地改善算法的全局收敛性,提高搜索效率.     

基于种群多样度的变参数遗传算法的研究

该文针对基本遗传算法（SGA）所存在的缺陷——早熟现象进行了分析,并在此基础上提出了基于种群多样度的变参数遗传算法（VPGA）。该算法从概率角度分析了遗传操作算子的作用,搜索范围以及多样性的影响,依据种群的多样度对遗传算法的参数进行自动调节,抑制早熟现象。并应用两种遗传算法对评价遗传算法性能的四个著名测试函数进行了仿真测试,仿真结果表明该算法相对于基本遗传算法的优越性和抑制早熟现象的有效性。     

多种群退火贪婪混合遗传算法

遗传算法是应用比较广泛的一种随机优化算法,遗传算法的收敛速度与问题解的质量是影响算法寻优性能的一对主要矛盾。为了提高遗传算法的性能,论文通过将局部搜索能力较强的贪婪算法引入遗传算法,并且同模拟退火和多种群并行遗传进化思想有机结合起来的方法,提出了一个改进型的算法——多种群退火贪婪混合遗传算法(MultigroupAnnealingGreedyHybridGeneticAlgorithm,简称MAGHGA)。仿真结果表明,该算法避免了在遗传算法中存在的早熟收敛问题,增强了算法的全局收敛性,同时也有效地提高了算法的收敛速度。     

基于多种群遗传算法测试用例优先级技术研究

测试用例优先级技术是一种高效实用的回归测试技术.为提高回归测试效率,提出了一种应用于同归测试过程中基于多种群遗传算法测试用例优先级技术的方法.该方法采用三个具有不同进化规律的种群,第一个种群重视全局搜索,第二个种群重视局部搜索,第三个种群通过前两个种群的移入来均衡算法的局部搜索和全局搜索能力,使算法能在更大范围内寻优....     

Embedding linear programming in multi objective genetic algorithms for reducing the size of the search space with application to leakage minimization in water distribution networks

This paper shows how embedding a local search algorithm, such as the iterated linear programming (LP), in the multi-objective genetic algorithms (MOGAs) can lead to a reduction in the search space and then to the improvement of the computational efficiency of the MOGAs. In fact, when the optimization problem features both continuous real variables and discrete integer variables, the search space can be subdivided into two sub-spaces, related to the two kinds of variables respectively. The problem can then be structured in such a way that MOGAs can be used for the search within the sub-space of the discrete integer variables. For each solution proposed by the MOGAs, the iterated LP can be used for the search within the sub-space of the continuous real variables. An example of this hybrid algorithm is provided herein as far as water distribution networks are concerned. In particular, the problem of the optimal location of control valves for leakage attenuation is considered. In this framework, the MOGA NSGAII is used to search for the optimal valve locations and for the identification of the isolation valves which have to be closed in the network in order to improve the effectiveness of the control valves whereas the iterated linear programming is used to search for the optimal settings of the control valves. The application to two case studies clearly proves the reduction in the MOGA search space size to render the hybrid algorithm more efficient than the MOGA without iterated linear programming embedded.     

Stochastic sampling design using a multi-objective genetic algorithm and adaptive neural networks

This paper presents a novel multi-objective genetic algorithm (MOGA) based on the NSGA-II algorithm, which uses metamodels to determine optimal sampling locations for installing pressure loggers in a water distribution system (WDS) when parameter uncertainty is considered. The new algorithm combines the multi-objective genetic algorithm with adaptive neural networks (MOGA–ANN) to locate pressure loggers. The purpose of pressure logger installation is to collect data for hydraulic model calibration. Sampling design is formulated as a two-objective optimization problem in this study. The objectives are to maximize the calibrated model accuracy and to minimize the number of sampling devices as a surrogate of sampling design cost. Calibrated model accuracy is defined as the average of normalized traces of model prediction covariance matrices, each of which is constructed from a randomly generated sampling set of calibration parameter values. This method of calculating model accuracy is called the ‘full’ fitness model. Within the genetic algorithm search process, the full fitness model is progressively replaced with the periodically (re)trained adaptive neural network metamodel where (re)training is done using the data collected by calling the full model. The methodology was first tested on a hypothetical (benchmark) problem to configure the setting requirement. Then the model was applied to a real case study. The results show that significant computational savings can be achieved by using the MOGA–ANN when compared to the approach where MOGA is linked to the full fitness model. When applied to the real case study, optimal solutions identified by MOGA–ANN are obtained 25 times faster than those identified by the full model without significant decrease in the accuracy of the final solution.     

基于MOGA算法的??∞ 回路成形直升机姿态控制器设计

提出一种改进的显模型跟踪??∞回路成形控制方法, 利用??_∞ 回路成形算法补偿显模型跟踪算法中前馈模型逆的不确定性. 针对??_∞ 回路成形控制算法中权重函数选取的盲目性, 利用多目标遗传算法, 结合改进的小生境淘汰技术对权重函数进行寻优, 以提高设计效率和准确性. 基于所提出的方法设计直升机的内回路显模型跟踪??∞ 回路成形姿态控制系统, 能够提高系统的鲁棒性.

     

Multi-objective genetic algorithms for cost-effective distributions of actuators and sensors in large structures

This paper proposes a multi-objective genetic algorithm (MOGA) for optimal placements of control devices and sensors in seismically excited civil structures through the integration of an implicit redundant representation genetic algorithm with a strength Pareto evolutionary algorithm 2. Not only are the total number and locations of control devices and sensors optimized, but dynamic responses of structures are also minimized as objective functions in the multi-objective formulation, i.e., both cost and seismic response control performance are simultaneously considered in structural control system design. The linear quadratic Gaussian control algorithm, hydraulic actuators and accelerometers are used for synthesis of active structural control systems on large civil structures. Three and twenty-story benchmark building structures are considered to demonstrate the performance of the proposed MOGA. It is shown that the proposed algorithm is effective in developing optimal Pareto front curves for optimal placement of actuators and sensors in seismically excited large buildings such that the performance on dynamic responses is also satisfied.     

模拟电路的多目标优化与演化设计

对模拟电路设计中涉及的多个目标进行了定义与量化,并针对这些目标提出一种面向模拟电路演化设计的多目标遗传算法,该方法利用非支配排序和适应值共享策略来提高搜索方向的空间均匀性,引入基于电路构造指令的编码方案来支持电路自动生成和提高电路演化的效率,并且该编码方案也同样适用于数字电路。利用协同演化的适应值评估策略来增强种群的学习能力,提高演化效率。实验结果表明,该方法可以设计出更实用、简单的模拟电路。     

An adaptive multi-population genetic algorithm to solve the multi-objective group scheduling problem in hybrid flexible flowshop with sequence-dependent setup times

In this paper we consider a multi-objective group scheduling problem in hybrid flexible flowshop with sequence-dependent setup times by minimizing total weighted tardiness and maximum completion time simultaneously. Whereas these kinds of problems are NP-hard, thus we proposed a multi-population genetic algorithm (MPGA) to search Pareto optimal solution for it. This algorithm comprises two stages. First stage applies combined objective of mentioned objectives and second stage uses previous stage’s results as an initial solution. In the second stage sub-population will be generated by re-arrangement of solutions of first stage. To evaluate performance of the proposed MPGA, it is compared with two distinguished benchmarks, multi-objective genetic algorithm (MOGA) and non-dominated sorting genetic algorithm II (NSGA-II), in three sizes of test problems: small, medium and large. The computational results show that this algorithm performs better than them.     

一种改进的基于NSGA-II和DE的多目标混合进化算法

为提高非支配排序遗传算法（NSGA-II）的搜索精度和多样性,本文借鉴差分进化中加强局部搜索的策略,提出了一种改进的NSGA-II算法（LDMNSGA-II）。该算法利用拉丁超立方体抽样技术对解种群进行初始化,保证种群的初始分布能够均匀,采用差分进化中的变异引导算子和交叉算子替换NSGA-II的交叉算子,加强局部搜索能力和提高搜索精度,同时保留NSGA-II中的变异算子,保留算法多样性。四个经典测试函数的仿真结果表明,文中算法LDMNSGA-II在解决多目标优化问题中表现出良好的综合性能。     

多目标遗传算法及在过程优化综合中的应用

化工过程的多目标优化综合问题可归结为多目标混合整数非线性规划(MOMINLP)模型的求解,求解方法主要有数学规划法和多目标进化算法。以多目标遗传算法(MOGA)为代表的进化算法被认为是特别适合求解此类问题。遗传算法大多用于单目标问题的优化,近十几年来将遗传算法应用到多目标优化的研究得到了很大的发展。本文对多目标遗传算法的一些重要概念、发展历程进行了回顾。针对化工过程的模型特点,对MOGA在过程综合中的应用研究进行了讨论,并认为混合遗传算法应是求解此类问题的有效算法。     

A multi-objective hyper-heuristic based on choice function

Hyper-heuristics are emerging methodologies that perform a search over the space of heuristics in an attempt to solve difficult computational optimization problems. We present a learning selection choice function based hyper-heuristic to solve multi-objective optimization problems. This high level approach controls and combines the strengths of three well-known multi-objective evolutionary algorithms (i.e. NSGAII, SPEA2 and MOGA), utilizing them as the low level heuristics. The performance of the proposed learning hyper-heuristic is investigated on the Walking Fish Group test suite which is a common benchmark for multi-objective optimization. Additionally, the proposed hyper-heuristic is applied to the vehicle crashworthiness design problem as a real-world multi-objective problem. The experimental results demonstrate the effectiveness of the hyper-heuristic approach when compared to the performance of each low level heuristic run on its own, as well as being compared to other approaches including an adaptive multi-method search, namely AMALGAM.