共查询到20条相似文献,搜索用时 109 毫秒
1.
基于遗传算法求解TSP问题的一种算法 总被引:12,自引:1,他引:12
TSP问题是一个经典的NP难度的组合优化问题,遗传算法是求解TSP问题的有效方法之一。利用交换启发交叉算子实现局部搜索加快算法的收敛速度和利用变换变异算子维持群体的多样性防止算法早熟收敛,给出了一种求解TSP问题的遗传算法。仿真实验结果表明了该算法的有效性和可行性。 相似文献
2.
求解TSP问题的一种改进的遗传算法 总被引:33,自引:5,他引:33
TSP问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种理想方法。文章针对解决TSP问题,提出使用改进的遗传算法,即用浓度控制选择策略以保证群体的多样性,用贪婪交叉算子和启发式倒位变异算子来提高算法的收敛速度,较好地解决了群体的多样性和收敛速度的矛盾。算法的分析和测试表明,该文算法的改进是有效的。 相似文献
3.
一种改进的遗传算法及其在TSP中的实现 总被引:4,自引:1,他引:4
TSP问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种方法。文章针对TSP问题.提出了一种改进的遗传算法。在遗传算法中引入进化算法的思想,在此基础上提出顶端培育策略和分阶段策略,以求在保证群体多样性的同时加快收敛速度。在算法的仿真和测试中,改进后的算法明显优于传统的遗传算法。这表明,该算法具有良好的可行性和实用性。 相似文献
4.
为了改善和声记忆库群体多样性, 提高算法的全局寻优能力, 在度量群体多样性指标的基础上, 从参数动态调整方法、和声记忆库更新策略两个方面对基本和声搜索算法进行了改进, 提出了多样性保持的和声搜索算法, 并将该算法应用于TSP的求解。结合TSP问题特点, 设计了基于交换和插入算子的和声微调方法。实例优化结果表明, 改进后的算法不容易陷入局部最优, 优化性能显著提高。 相似文献
5.
TSP问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种方法.文章针对TSP问题,提出了一种改进的遗传算法.在遗传算法中引入进化算法的思想,在此基础上提出顶端培育策略和分阶段策略,以求在保证群体多样性的同时加快收敛速度.在算法的仿真和测试中,改进后的算法明显优于传统的遗传算法.这表明,该算法具有良好的可行性和实用性. 相似文献
6.
TSP问题(旅行商问题)是组合优化问题中最经典的NP问题之一,蚁群算法是基于群体的一种仿生算法,为求解复杂的组合优化问题提供了一种新思路,本文讨论了如何用基本的蚁群算法来求解TSP问题。 相似文献
7.
十进制MIMIC算法是基于MIMIC二进制编码算法思想的可用来求解TSP的离散分布估计算法。着重考虑该算法在较大规模TSP问题上的算法缺陷,对其编码方式和概率模型进行了改进,提出了新的个体生成策略,在初始化种群阶段使用了贪心算法,在进化过程中引入了杂交算子、变异算子、映射算子、优化算子等演化算子,采用了动态调整方法来确定优势群体的规模。以上改进使得算法在小种群解大规模TSP问题的情况下仍可保持种群的多样性。实验结果表明,改进算法在求解规模、求解质量和寻优速度上都有明显提高。 相似文献
8.
免疫遗传算法在TSP求解中的应用 总被引:4,自引:0,他引:4
基本遗传算法保持群体多样性的能力较差,所以经常在问题求解的过程中得到局部最优解。根据生物的免疫原理提出的一种改进算法——免疫遗传算法。免疫遗传算法主要体现了生物免疫系统中的基因重组、免疫记忆、隔离小生境和免疫元动态等特性,这些特性改进基本遗传算法的群体多样性保持能力。最后结合旅行商问题(TSP)的优化介绍了具体实现方法,实验结果表明该免疫遗传算法有较好的性能。 相似文献
9.
WANG Hui 《数字社区&智能家居》2008,(12)
针对TSP问题,提出了一种基于自适应评价函数的改进的遗传算法,并且给出选择、交叉和变异操作的设计,实验表明算法维持了群体的多样性,防止算法过早收敛而陷入局部最优解,更有效地搜出全局近似最优解。 相似文献
10.
求解TSP的一种改进遗传算法 总被引:14,自引:0,他引:14
TSP问题是典型的NP-hard组合优化问题,GA是求解此类问题的一种方法。但它存在如何较快地找到最优解并防止“早熟”收敛的问题。文章针对上述问题并结合TSP问题的特点,提出了改进的遗传算法。它从相似性的思想出发,按适应值相似性将群体分级,在不同的级内采用不同的操作,产生数目不等的新解并利用加速算子使其更接近局部极小值。改进后的算法较好地解决了群体多样性与收敛性的矛盾。实验结果表明,该文算法的改进是有效的。 相似文献
11.
12.
13.
Ben-Da Zhou Hong-Liang Yao Ming-Hua Shi Qin Yue Hao Wang 《Knowledge and Information Systems》2012,31(2):389-403
The deficiencies of keeping population diversity, prematurity and low success rate of searching the global optimal solution
are the shortcomings of genetic algorithm (GA). Based on the bias of samples in the uniform design sampling (UDS) point set,
the crossover operation in GA is redesigned. Using the concentrations of antibodies in artificial immune system (AIS), the
chromosomes concentration in GA is defined and the clonal selection strategy is designed. In order to solve the maximum clique
problem (MCP), an new immune GA (UIGA) is presented based on the clonal selection strategy and UDS. The simulation results
show that the UIGA provides superior solution quality, convergence rate, and other various indices to those of the simple
and good point GA when solving MCPs. 相似文献
14.
针对GA早熟收敛问题研究中存在的种群多样性定义缺乏统一性和普适性问题,基于GA基因层次种群多样性的本质,建立了实数和二进制编码的GA层次多样性的统一数学模型。首先,将实数编码GA的种群矩阵等效变换成与二进制编码GA种群矩阵相同的形式。其次,定义了类随机变量的概念及其特性指标:数学期望、偏离度以及方差;在此基础上建立了适于两种编码的种群多样性的统一模型,并给出了该模型的进化矩阵和图形化两种表示方法。对GA测试函数的仿真分析表明,该模型可以有效地体现和分析GA进化过程中种群多样性的变化趋势以及各基因位的收敛过程和收敛结果。最后,指出了进一步的分析思路和方向。 相似文献
15.
基于种群多样性指导的遗传算法 总被引:5,自引:2,他引:5
分析了遗传算法各个阶段对种群多样性影响,并给出了各阶段以种群多样性测度来指导操作策略,避免局部收敛。结合一个多峰函数给出其用MATLAB语言运行试验结果。仿真试验表明,由于在各个阶段都注意了种群的多样性,能够对函数进行全局寻优,但对进化收敛速度有一定影响。 相似文献
16.
17.
18.
Bilal Alataş Erhan Akin 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2006,10(3):230-237
In this paper, a genetic algorithm (GA) is proposed as a search strategy for not only positive but also negative quantitative
association rule (AR) mining within databases. Contrary to the methods used as usual, ARs are directly mined without generating
frequent itemsets. The proposed GA performs a database-independent approach that does not rely upon the minimum support and
the minimum confidence thresholds that are hard to determine for each database. Instead of randomly generated initial population,
uniform population that forces the initial population to be not far away from the solutions and distributes it in the feasible
region uniformly is used. An adaptive mutation probability, a new operator called uniform operator that ensures the genetic
diversity, and an efficient adjusted fitness function are used for mining all interesting ARs from the last population in
only single run of GA. The efficiency of the proposed GA is validated upon synthetic and real databases. 相似文献
19.
20.
A Locating Method for Reliability-Critical Gates with a Parallel-Structured Genetic Algorithm 下载免费PDF全文
Jie Xiao Zhan-Hui Shi Jian-Hui Jiang Xu-Hua Yang Yu-Jiao Huang Hai-Gen Hu 《计算机科学技术学报》2019,34(5):1136-1151
The reliability allowance of circuits tends to decrease with the increase of circuit integration and the application of new technology and materials, and the hardening strategy oriented toward gates is an effective technology for improving the circuit reliability of the current situations. Therefore, a parallel-structured genetic algorithm (GA), PGA, is proposed in this paper to locate reliability-critical gates to successfully perform targeted hardening. Firstly, we design a binary coding method for reliability-critical gates and build an ordered initial population consisting of dominant individuals to improve the quality of the initial population. Secondly, we construct an embedded parallel operation loop for directional crossover and directional mutation to compensate for the deficiency of the poor local search of the GA. Thirdly, for combination with a diversity protection strategy for the population, we design an elitism retention based selection method to boost the convergence speed and avoid being trapped by a local optimum. Finally, we present an ordered identification method oriented toward reliability-critical gates using a scoring mechanism to retain the potential optimal solutions in each round to improve the robustness of the proposed locating method. The simulation results on benchmark circuits show that the proposed method PGA is an efficient locating method for reliability-critical gates in terms of accuracy and convergence speed. 相似文献