基于TSP问题的一种改进遗传算法

针对传统遗传算法(GA)在解决旅行商问题(TSP)时存在的不足,对初始种群的选取方式和算子的选取进行了改进,设计出了一种能够较好的求解出TSP问题的最优解的算法.计算机仿真实验验证了该算法的有效性.     

分层混合局部搜索策略异构多核系统调度

针对遗传算法解决异构多核系统的任务调度问题容易产生早熟现象及其局部寻优能力较差的缺点,将局部搜索算法与遗传算法相结合,创新性地提出一种求解异构多核系统的任务调度问题的分层混合局部搜索遗传算法。该算法提出一种新的分层优化策略以产生初始种群,在变异操作中,对部分个体设计3-opt优化变异,对种群中的优秀个体用改进的Lin-Kernighan算法进行优化。仿真实验结果表明,分层混合局部搜索遗传算法求解异构多核系统的任务调度问题时可以高效获得高质量的解。     

解特殊工艺约束下提前/拖后调度问题的新遗传算法

针对非一致并行机环境下特殊工艺约束提前/拖后调度问题,设计了一个基于向量组编码的新遗传算法,此算法的编码方法简单,能有效地反映实际调度方案,即清楚地反映出每机器加工产品的代号和顺序.引入浓度概念,对种群中浓度高的个体进行抑制,从而增加群体多样性,同时,利用爬山算法对种群中个体进行局部搜索,提高了种群质量,加快了收敛速度.仿真结果表明,此算法是有效的,适用于解实际的此类调度问题.     

求解TSP的子空间遗传算法

为避免遗传算法在计算过程中搜索冗余空间而耗费不必要的资源及时间，本提出了一种以经费遗传算法为基础，通过分析问题的特殊解集，以找出原问题解空间的区域特征从而构造出缩小算法搜索空间的子空间遗传算法，并用它求解TSP。结果表明，该算法实施起来非常有效。     

自适应多种群回溯群居蜘蛛算法求解TSP问题

在群居蜘蛛优化算法中引入自适应决策半径,将蜘蛛种群动态地分成多个种群,种群内适应度不同的个体采取不同的更新方式.在筛选全局极值的基础上,根据进化程度执行回溯迭代更新,提出一种自适应多种群回溯群居蜘蛛优化算法,旨在提高种群样本多样性和算法全局寻优能力.函数寻优结果表明改进算法具有较快的收敛速度和较高的收敛精度.最后将其应用于TSP问题的求解.     

TSP的量子蚂蚁算法求解

在分析量子算法的基本概念的基础上,提出了一种新的算法——量子蚂蚁算法。量子蚂蚁算法结合了量子计算中量子旋转门的量子信息和蚂蚁寻优的特点,为解决实际问题提供的一种新的优化方法。本文将量子蚂蚁算法应用于TSP问题的研究,通过选取国际通用的TSP实例库中多个实例进行测试,表明了新算法具有很好的精确度和鲁棒性,即使对于大规模问题,也能以很小的种群和不长的时间求得相对误差较小的满意解。     

基于改进遗传算法的集合覆盖问题

集合覆盖问题是组合优化中的典型问题,在日常生活中有着广泛的应用.提出了一种改进遗传算法来解决集合覆盖问题.算法对标准遗传算法的改进主要表现在:1)结合启发式算法和随机生成,设计了新的产生初始种群的方法;2)引入修补操作处理不可行解使其转换成可行解;3)对重复个体进行处理再利用;4)对多点交叉进行推广,提出了新的交叉算子;5)针对可行解和不可行解,采取两种自适应多位变异操作.数值实验结果表明该算法对于解决规模较大的集合覆盖问题是有效的.     

一种改进适应度函数的遗传算法

针对遗传算法搜索导优中适应度函数的设计不当,将难以体现个体差异和选择操作的作用,从而造成早熟收敛的问题,构建了两种基于顺序的适应度函数的模型.适应度函数的设计使得在进化过程中控制选择压力,种群竞争力得到增强,早熟现象得到改善.并将改进的算法应用在复杂函数优化问题上,MATLAB优化结果表明,算法在种群多样性、搜索速度、计算精度上均有改善,推动遗传算法在工程领域的应用.     

改进遗传算法求解TSP问题

提出了一种改进遗传算法求解 TSP.该方法在迭代初期引入不适应度函数作为评价标准 ,结合启发式交叉和边重组交叉算子设计了一种新的交叉算子 ,并对变异后个体进行免疫操作 .此外对操作后群体进行整理 ,删除群体中相同个体 ,得到规模为 N1的中间群体 ,对较优的 N -N 1个个体进行启发式变异 ,并将变异后个体补充进中间群体 ,生成规模为 N的新群体 ,这样保证群体中没有相同个体 ,从而保证群体多样性 .数值结果表明这种改进遗传算法是有效的 .     

面向多目标优化的一种混合进化算法

针对多目标优化问题,设计一种基于量子计算和非支配排序遗传算法相结合的智能算法进行求解,综合量子算法和非支配排序遗传算法的优点,在局部搜索和全局搜索之间进行权衡。混合算法采用量子比特对问题的解进行编码,基于量子旋转门算子、分散交叉算子以及高斯变异算子对种群进行更新。进行局部深入搜索时,用一个解在目标空间中跟理想点的距离来评价该解的优劣;进行全局搜索时,基于非支配排序遗传算法中的有效前沿的划分和解之间的拥挤距离来评价某个解。最后,在经典的测试函数ZDT5上对所提混合算法进行了测试。通过对比分析若干项针对有效解集的评价指标,该混合算法在跟最优有效前沿的逼近程度以及有效解集分布的均匀程度上均优于目前得到广泛应用的非支配排序遗传算法。     

Performance characteristics of alternative genetic algorithmic approaches to the traveling salesman problem using path representation: An empirical study

The potential of Genetic Algorithmic (GA) approaches for solving order-based problems including the Traveling Salesman Problem (TSP) is recognized in a number of recent studies. By applying various GAs, these studies developed a set of unresolved GA design and configuration issues. The purpose of this study is to resolve the conflicting GA design and configuration issues by (1) concentrating on the classical TSP; and (2) developing, implementing, and testing a complete set of alternative GA configurations, 144 GAs are developed and evaluated by solvinh 5000 TSPs. A carefully designed statistical experimental plan accompanied by rigorous statistical analysis isolate the most promising configurations and identify their effect on solution time and quality. Although, the emphasis is on the TSP, the final results are applicable to other order-based problems that use sequence encoding.     

The efficiency of hybrid mutation genetic algorithm for the travelling salesman problem

In this paper, we present an efficient genetic algorithm (GA) for solving the travelling salesman problem (TSP) as a combinatorial optimization problem. In our computational model, we propose a complete subtour exchange crossover that does not break as some good subtours as possible, because the good subtours are worth preserving for descendants. Generally speaking, global search GA is considered to be better approaches than local searches. However, it is necessary to strengthen the ability of local search as well as global ones in order to increase a GA total efficiency. In this study, our GA applies a stochastic hill climbing procedure in the mutation process of the GA. Experimental results showed that the GA leads good convergence as high as 99 percent even for 500 cities TSP.     

Particle methods for multi-group pedestrian flow

We consider a multi-group microscopic model for pedestrian flow describing the behaviour of large groups. It is based on an interacting particle system coupled to an eikonal equation. Hydrodynamic multi-group models are derived from the underlying particle system as well as scalar multi-group models. The eikonal equation is used to compute optimal paths for the pedestrians. Particle methods are used to solve the equations on all levels of the hierarchy. Numerical test cases are investigated and the models and, in particular, the resulting evacuation times are compared for a wide range of different parameters.     

改进遗传算法求解旅行商问题

针对采用自然编码的遗传算法在求解旅行商问题(TSP)过程中初始群体设置过于复杂的问题,采用了Grefenstette编码设置初始群体,有效保证了初始群体的随机性和多样性.同时,在遗传算法实施过程中采用了自然编码,吸取边重组交叉算子和简单交叉算子的优点,提出一种新的交叉算子.这种处理解决了Grefenstette编码在遗传算法的交叉和变异过程中只能部分遗传父代的优良特性的问题.对TSP试算结果表明,采用这种遗传算法策略有利于问题的求解.这种实施的策略可以大量用于加工领域和交通领域以及其他规划领域的路径规划中.     

Improved Linear Programming Formulations for the Multi-group Discriminant Problem

This paper sets out to solve the multi (more than two)-group classification problem, and develops a new linear programming model which simultaneously determines the cut-off values for the different classification functions. Instead of decomposing the content in the multi-group problem to facilitate computation of the cut-off values, this new model aggregates information contained in the multi-group problem which, intuitively, should provide better estimates of the group boundaries. Furthermore, this new model, one existing LP model, and a statistical approach will be tested by using real-life data.     

A new population seeding technique for permutation-coded Genetic Algorithm: Service transfer approach

Genetic Algorithm (GA) is a popular heuristic method for dealing complex problems with very large search space. Among various phases of GA, the initial phase of population seeding plays an important role in deciding the span of GA to achieve the best fit w.r.t. the time. In other words, the quality of individual solutions generated in the initial population phase plays a critical role in determining the quality of final optimal solution. The traditional GA with random population seeding technique is quite simple and of course efficient to some extent; however, the population may contain poor quality individuals which take long time to converge with optimal solution. On the other hand, the hybrid population seeding techniques which have the benefit of good quality individuals and fast convergence lacks in terms of randomness, individual diversity and ability to converge with global optimal solution. This motivates to design a population seeding technique with multifaceted features of randomness, individual diversity and good quality. In this paper, an efficient Ordered Distance Vector (ODV) based population seeding technique has been proposed for permutation-coded GA using an elitist service transfer approach. One of the famous combinatorial hard problems of Traveling Salesman Problem (TSP) is being chosen as the testbed and the experiments are performed on different sized benchmark TSP instances obtained from standard TSPLIB [54]. The experimental results advocate that the proposed technique outperforms the existing popular initialization methods in terms of convergence rate, error rate and convergence time.     

Experimental analysis of heuristics for the bottleneck traveling salesman problem

In this paper we develop efficient heuristic algorithms to solve the bottleneck traveling salesman problem (BTSP). Results of extensive computational experiments are reported. Our heuristics produced optimal solutions for all the test problems considered from TSPLIB, JM-instances, National TSP instances, and VLSI TSP instances in very reasonable running time. We also conducted experiments with specially constructed ‘hard’ instances of the BTSP that produced optimal solutions for all but seven problems. Some fast construction heuristics are also discussed. Our algorithms could easily be modified to solve related problems such as the maximum scatter TSP and testing hamiltonicity of a graph.     

Construction heuristics for the asymmetric TSP

Non-Euclidean traveling salesman problem (TSP) construction heuristics, and especially asymmetric TSP construction heuristics, have been neglected in the literature by comparison with the extensive efforts devoted to studying Euclidean TSP construction heuristics. This state of affairs is at odds with the fact that asymmetric models are relevant to a wider range of applications, and indeed are uniformly more general that symmetric models. Moreover, common construction approaches for the Euclidean TSP have been shown to produce poor quality solutions for non-Euclidean instances. Motivation for remedying this gap in the study of construction approaches is increased by the fact that such methods are a great deal faster than other TSP heuristics, which can be important for real time problems requiring continuously updated response. The purpose of this paper is to describe two new construction heuristics for the asymmetric TSP and a third heuristic based on combining the other two. Extensive computational experiments are performed for several different families of TSP instances, disclosing that our combined heuristic clearly outperforms well-known TSP construction methods and proves significantly more robust in obtaining (relatively) high quality solutions over a wide range of problems.     

经过改进的求解TSP问题的蚁群算法

介绍了一种求解TSP问题的算法—改进的蚁群算法,算法通过模拟蚁群搜索食物的过程,可用于求解TSP问题,算法的主要特点是:正反馈、分布式计算、与某种启发式算法相结合.通过对传统蚁群算法的改进可以得到较好的结果.计算机仿真结果表明了该算法的有效性.