基于混合粒子群算法求解TSP问题

遗传算法是研究TSP问题中最为广泛的一种算法,它具有全局搜索的能力。而粒子群算法收敛速度较快,但容易造成局部最优的情况。本文基于遗传算法的交叉变异设计了混合粒子群算法,通过对TSP问题求解分析,证实该方法提高了标准粒子群的搜索能力,获得了较高的收敛速度和近似最优解。     

基于蚁群算法的面向服务软件的部署优化方法

面向服务软件的部署优化问题是典型的NP难题.本文构建了基于性能改善的软件部署优化模型,设计了一种蚁群优化算法ACO-DO进行近似最优解的快速求解.该算法通过设计基于部署优化问题的启发式、改进部署方案的构建顺序、增加局部搜索过程实现蚁群算法求解效率的提升.通过不同规模的实例实验,验证了ACO-DO算法能够取得比现有的混合整数线性规划算法、蚁群算法和遗传算法更好的性能.     

一种混合遗传LM算法求解非线性最小二乘问题

文章提出了一种混合遗传LM算法,并将其用于求解非线性最小二乘问题,该方法利用遗传算法摆脱局部最小值,在全局极小值的领域内估计解,找到全局最小值的近似后,利用遗传算法找到的全局最优解作为LM算法的起点。像遗传算法这样的随机搜索算法可以很容易地在全局最小值附近计算出一个解,但由于搜索的随机性,需要很长时间才能收敛到精确的最小值。因此,该算法协同结合了确定性局部搜索和启发式随机全局搜索的优点,高效地计算出精确的解。利用了一个圆柱拟合的实验来验证该算法,结果表明该算法在拟合问题上有良好的性能。     

SVDD参数优化的有限穷举—局部遗传算法及故障检测应用

针对支持向量数据描述(SVDD)训练过程中的参数优化问题,提出了一种有限穷举—局部遗传算法.首先,在分别分析参数C和σ对SVDD分类性能不同影响的基础上,得到参数σ是影响分类性能主因的结论.然后针对σ的优化问题,通过穷举有限个整数解并比较其分类性能来确定近似最优解,在近似最优解的领域内用遗传算法进行局部搜索,最终得到精确的优化参数.仿真实验及电路故障检测应用结果表明:算法有效避免了参数搜索的盲目性,能以更短的时耗逼近最优解.     

基于遗传算法的模糊关系方程求解

针对模糊关系方程的求解问题,即模糊综合评判逆问题,提出了一种基于遗传算法的求解方法.算法能有效地找出模糊关系方程的全局近似最优解,并且与模糊关系合成算子的具体形式无关,有良好的鲁棒性和自适应能力.仿真结果表明,此方法是一种有效、实用的模糊关系方程求解方法.     

基于遗传算法求解线性规划问题

遗传算法是模仿自然界的"优胜劣汰"原理设计的一种近似方法。本文利用遗传算法求解一类线性规划问题,并给出了遗传算法的算法,通过两个数值例子来说明了遗传算法来求解线性规划问题的有效性。     

求解DEC-POMDP问题的改进遗传算法

分布式部分可观测马尔科夫模型(Decentralized partially observable Markov decision progress,DEC-POMDP)是研究不确定性情况下多主体协同决策的重要模型。由于其求解难度是NEXP-complete,所以迄今为止尚没有有效的算法能求出其最优解。但是存在一部分近似求解的算法可以解决规模较小的问题。针对此问题,在遗传算法的基础上,通过引入最佳起始状态和最佳收益状态提出改进的遗传算法(Improved Genetic Algorithms,IGA),算法将问题的求解分为两个步骤,首先求解从给定起始状态到最佳起始状态的近似最优策略,然后求解在最佳收益状态之间转换的策略。通过实验可以看出IGA压缩了要搜索的策略空间,减小了编码长度,是求解DEC-POMDP的有效算法。     

基于自适应节点选择蚁群算法的QoS选播路由算法

针对基本蚁群算法在求解QoS选播路由问题中存在的容易陷入局部最优和收敛速度慢的缺陷,提出一种基于自适应节点选择的蚁群算法对该问题进行求解.该算法根据解的情况自适应调整节点选择策略;依据各路径上信息素的＂集中＂程度判断解的早熟、停滞情况,并对可能陷入局部最优的解进行信息素混沌扰动更新,以便跳出局部极值区间.仿真实验表明,算法全局搜索能力较强,能够跳出局部极值区间,快速地收敛到全局最优解,算法是可行、有效的.     

任务可定点拆分的资源受限项目调度问题研究

任务可定点拆分的资源受限项目调度问题是标准资源受限项目调度问题的一个扩展.针对这一问题提出了一种离散人工蜂群求解算法.离散人工蜂群算法中采用基于任务排列的食物源编码方式,并提出了能够一种保证解的可行性和离散型的候选食物源生成方法.项目中允许定点拆分的任务首先要转换为满足先序关系的分任务,然后在通过串行调度机制生成可行调度.实算表明,该算法能够有效求解任务可定点拆分的资源受限项目调度问题,同时也看到在不影响完成质量情况下,项目通过任务拆分能够在一定程度上缩短项目工期.     

雷达信号识别的GANN方法

利用神经网络方法进行雷达信号识别存在两个问题,一是难以选择最优的网络结构;二是用传统的BP学习算法,常常收敛到局部解。本文提出一种GANN方法,即首先利用遗传算法优化两层前馈神经网络结构以确定中间隐层的节点数,然后用遗传算法进行学习。通过与BP算法相比较,遗传算法不仅速度快,而且能找到最优解。实验表明,将GANN应用于雷达信号识别,识别率更高。     

The computation of polygonal approximations for 2D contours based on a concavity tree

In this work, a new proposal to improve some methods based on the merge approach to obtain polygonal approximations in 2D contours is presented. These methods use a set of candidate dominant points (CDPs) to obtain a polygonal approximation. Then, redundant candidate dominant points of the set of CDPs are deleted, and the remaining dominant points will be the polygonal approximation of the original contour. The main drawback of most of these methods is that they use all breakpoints as CDPs and most of these breakpoints depict only the noise of the original contour.Our proposal, based on a concavity tree, obtains a more reduced and significant set of CDPs. When this proposal is used by some methods based on the merge approach (the Masood methods and the Carmona method), their computation times are reduced. The experimental results show that the new proposal is efficient and improves the tested methods.     

A genetic algorithm with chromosome-repairing for min − # and min − ε polygonal approximation of digital curves

A genetic algorithm for solving min ? ε polygonal approximation and min ? # polygonal approximation is proposed in this paper. It combines traditional split-and-merge techniques with a novel chromosome-repairing scheme to cope with constraints. Due to this combination of techniques we call our new method SMCR. In this new scheme an infeasible solution cannot only be easily transformed into a feasible one, but also be optimized. The experimental results show that the proposed SMCR has higher performance than the other GA-based methods and some non-GA-based methods.     

A polygonal approximation of shape boundaries of marine plankton based-on genetic algorithms

Polygonal approximation of a shape boundary can provide a minimalistic representation of the shape. It can also accelerate the processing speed of feature extraction. Our interest is in applying such a method to approximate the boundaries of plankton shapes. A polygonal approximation method based on genetic algorithms has been designed to compactly describe the plankton shapes by polygons. Firstly, two artificial digital curves are used to test the performance of our algorithm. Results are compared with other existing algorithms which show that our algorithm has efficient performance for solving the problem of the polygonal approximation. Secondly, the proposed method is applied to a selection of plankton images under three different approximation levels to a polygonal fit and then five evaluation criteria are applied to determine which approximation level of a particular image is most suitable for describing the shape. The stability and robustness of three approximation levels are also tested.     

A fast O(N) multiresolution polygonal approximation algorithm for GPS trajectory simplification

Recent advances in geopositioning mobile phones have made it possible for users to collect a large number of GPS trajectories by recording their location information. However, these mobile phones with built-in GPS devices usually record far more data than needed, which brings about both heavy data storage and a computationally expensive burden in the rendering process for a Web browser. To address this practical problem, we present a fast polygonal approximation algorithm in 2-D space for the GPS trajectory simplification under the so-called integral square synchronous distance error criterion in a linear time complexity. The underlying algorithm is designed and implemented using a bottom-up multiresolution method, where the input of polygonal approximation in the coarser resolution is the polygonal curve achieved in the finer resolution. For each resolution (map scale), priority-queue structure is exploited in graph construction to construct the initialized approximated curve. Once the polygonal curve is initialized, two fine-tune algorithms are employed in order to achieve the desirable quality level. Experimental results validated that the proposed algorithm is fast and achieves a better approximation result than the existing competitive methods.     

用于约束优化的简洁多目标微粒群优化算法

本文提出了一种少控制参数的约束多目标微粒群优化算法.该算法利用关于微粒全局和个体最优点的高斯分布来更新微粒的位置,无需设置惯性权重和学习因子等控制参数;利用非可行储备集保存所得非可行解,给出一种改进的储备集更新方法;为均衡微粒对未知可行域和已知可行域的开发/探索能力,提出一种线性递减策略,用来分配微粒从非可行储备集中选...     

Polygonal approximation based on coarse-grained parallel genetic algorithm

This paper proposes to apply coarse-grained parallel genetic algorithm (CGPGA) to solve polygonal approximation problem. Chromosomes are used to represent digital curves and genes correspond to points of curves. This method divides the whole population into several subpopulations, each of which performs evolutionary process independently. After every migration interval number of generations, these subpopulations exchange their information with each other. Inspired by the designing theory of ensemble learning in machine learning, this paper further improves the basic CGPGA through adopting different but effective genetic algorithms, respectively, in different subpopulations. Both the diversity among different subpopulations and the accuracy in each individual subpopulation are ensured. Experimental results, based on four benchmark curves and four real image curves extracted from the lake maps, show that the basic CGPGA outperforms the used genetic algorithm, and further the improved CGPGA (ICGPGA) is more effective than the basic CGPGA, in terms of the quality of best solutions, the average solutions, and the variance of best solutions. Especially for those larger approximation problems, the ICGPGA is more remarkably superior to some representative genetic algorithms.     

一种使用遗传算法在高层次综合中完成互连优化的方法

提出一种使用遗传算法在高层次综合中完成互连优化的方法 .相比同类的研究 ,该方法的主要优势在于提出一种新颖的编码方法 ,并设计了相应的遗传算子 ,避免了在计算过程中不可行解的产生 .实验数据证明了该算法的有效性     

基于精确罚函数法的遗传算法求解时延约束组播路由问题

有时延约束的组播问题是通信网络多点路由优化问题中的重要部分,已被证明是NP-complete问题.本文提出了一种基于罚函数法的启发式遗传算法以求解该问题,并讨论了违反时延约束不可行解的罚函数选取问题,进化过程中采用适于此类问题的动态交配概率、变异概率以提高算法的收敛速度.最后分析了算法的复杂度.仿真表明,本文算法是有效的、稳定的.     

Design and Analysis of an Efficient Evolutionary Image Segmentation Algorithm

Evolutionary image segmentation algorithms have a number of advantages such as continuous contour, non-oversegmentation, and non-thresholds. However, most of the evolutionary image segmentation algorithms suffer from long computation time because the number of encoding parameters is large. In this paper, design and analysis of an efficient evolutionary image segmentation algorithm EISA are proposed. EISA uses a K-means algorithm to split an image into many homogeneous regions, and then uses an intelligent genetic algorithm IGA associated with an effective chromosome encoding method to merge the regions automatically such that the objective of the desired segmentation can be effectively achieved, where IGA is superior to conventional genetic algorithms in solving large parameter optimization problems. High performance of EISA is illustrated in terms of both the evaluation performance and computation time, compared with some current segmentation methods. It is empirically shown that EISA is robust and efficient using nature images with various characteristics.     

一种解决约束优化问题的模糊粒子群算法

该文针对复杂约束优化问题,提出了一种模糊粒子群算法(FPSO),设计了一个新的扰动算子,在此基础上定义了模糊个体极值和模糊全局极值,利用这两个定义改进了粒子群进化的方程,利用该方程更新粒子的速度与位置,可以避免早熟收敛问题;定义了不可行度阈值,利用此定义给出了新的粒子比较准则,该准则可以保留一部分性能较优的不可行解微粒。用概率论的有关知识证明了算法的收敛性。仿真结果表明,对于复杂约束优化问题,算法寻优性能优良,特别是对于超高维约束优化问题,该算法获得了更高精度的解。