多背包问题的遗传算法求解

本文提出了一种新的组合优化问题—多背包问题,并给出了它的基于0/1规划的数学模型;提出了解决多背包问题的遗传算法。该算法以目标函数加约束惩罚函数作为适应值函数,交叉算子选用了一致交叉的方法,仿真的结果表明该遗传算法在求解多背包问题上的表现是良好的。     

基于混合遗传算法和点面距离测度的深度像配准*

提出一种利用改进的遗传算法和点面距离作为误差测度的深度像精确配准算法。与现有ICP框架下的迭代算法不同,将深度像配准视为高维空间的一个优化问题,通过在遗传算法中加入退火选择、爬山法以及参数空间的动态退化来加速寻找最优的位置转换关系。同时,采用一种新的基于点面距离的适应函数来计算配准误差,使得算法具有更强的鲁棒性。实验结果表明,该算法不需要初始的运动参数估计,具有较高的配准精度,收敛速度快且抗噪声能力强。     

遗传算法机理的研究

众所周知,“模式定理”和“隐性并行性”是遗传算法(genetic algorithms,简称GA算法)的两大理论基础.该文对这两个原理进行分析,指出这两个原理存在有不严格和不足之处,即作为GA算法的基础,这两个原理尚欠完善.为加深对GA的理解,文章提出遗传算法的一个新的改进模型——理想浓度模型.通过对此模型的分析,得出遗传算法本质上是一个具有定向制导的随机搜索技术.其定向制导原则是,导向以适应度高的模式为祖先的染色体“家族”方向.最后给出两个典型的函数求最大值的模拟例子.从模拟结果看,改进后的GA算法大大提高了算法的速度,解的精度也有所提高.这说明新算法具有应用的潜力.     

改进的遗传算法在医学图像中的应用

针对标准的遗传算法（ GA）在优化Otsu法求取图像阈值时出现收敛速度慢、易早熟等问题,提出了一种改进的GA用于图像分割。该算法根据种群不同的进化代数和个体适应度的大小,动态地调整精英选择策略和遗传算子,从而提高了算法的收敛速度、得到了范围稳定的图像分割阈值,且保持了种群多样性。将该算法应用于医学图像分割,实验结果表明：该算法可以对医学图像进行分割且效果明显。     

交互式遗传算法中用户评估方法研究

交互式遗传算法是针对一些应用领域存在的适应度函数难以明确表达的问题,通过用户参与遗传操作过程,对进化个体进行评估以代替计算过程的一种改进方法.但交互式遗传算法存在的一个主要问题是当遗传操作的收敛速度慢时,用户需对大量个体进行评估,尤其是在个体间相似程度较高时,容易产生疲劳现象.针对这种问题,本文提出了两种方法来提高收敛性,缩短评估过程,从而最终解决用户疲劳问题.对人脸识别问题的实验结果表明本文算法可以有效的解决用户疲劳问题.     

交互式遗传算法中用户评估质量和收敛性能提高

交互式遗传算法主要是针对一些应用领域存在的适应度函数难以明确表达的问题,通过用户参与遗传操作过程,对进化个体进行评估以代替计算过程的一种改进方法。但交互式遗传算法存在的主要问题是:当遗传操作的收敛速度慢时,用户需对大量个体进行评估,尤其是在个体间相似程度较高时,容易产生疲劳现象。针对这种问题,本文提出三种方法来提高收敛性及评估过程的质量。在人脸图形上所做的实验结果表明,算法可以有效地缓解用户的疲劳问题。     

基于并行遗传算法的气球力Snake模型参数优化

针对气球力Snake模型的图像分割效果很大限度上依赖于初始参数的选取,借鉴遗传算法的高效、并行和全局搜索的性能,提出了一种求解气球力Snake模型最优参数的算法。该算法用气球力Snake能量泛函作为目标函数,引入图像相似度函数作为遗传迭代终止准则,采用并行遗传计算进行分割参数寻优。实际医学图像的实验结果表明,算法能避免通过大量实验来人工选取参数的繁琐,也解决了参数选取不当导致的分割结果不理想的问题,可以得到较好的分割效果。     

An application of a GA with Markov network surrogate to feature selection

Surrogate models of fitness have been presented as a way of reducing the number of fitness evaluations required by evolutionary algorithms. This is of particular interest with expensive fitness functions where the time taken for building the model is outweighed by the savings of using fewer function evaluations. In this article, we show how a Markov network model can be used as a surrogate fitness function for a genetic algorithm in a new algorithm called Markov Fitness Model Genetic Algorithm (MFM-GA). We thoroughly investigate its application to a fitness function for feature selection in Case-Based Reasoning (CBR), using a range of standard benchmarks from the CBR community. This fitness function requires considerable computation time to evaluate and we show that using the surrogate offers a significant decrease in total run-time compared to a GA using the true fitness function. This comes at the cost of a reduction in the global best fitness found. We demonstrate that the quality of the solutions obtained by MFM-GA improves significantly with model rebuilding. Comparisons with a classic GA, a GA using fitness inheritance and a selection of filter selection methods for CBR shows that MFM-GA provides a good trade-off between fitness quality and run-time.     

Genetic algorithm and self organizing map based fuzzy hybrid intelligent method for color image segmentation

The grouping of pixels based on some similarity criteria is called image segmentation. In this paper the problem of color image segmentation is considered as a clustering problem and a fixed length genetic algorithm (GA) is used to handle it. The effectiveness of GA depends on the objective function (fitness function) and the initialization of the population. A new objective function is proposed to evaluate the quality of the segmentation and the fitness of a chromosome. In fixed length genetic algorithm the chromosomes have same length, which is normally set by the user. Here, a self organizing map (SOM) is used to determine the number of segments in order to set the length of a chromosome automatically. An opposition based strategy is adopted for the initialization of the population in order to diversify the search process. In some cases the proposed method makes the small regions of an image as separate segments, which leads to noisy segmentation. A simple ad hoc mechanism is devised to refine the noisy segmentation. The qualitative and quantitative results show that the proposed method performs better than the state-of-the-art methods.     

基于二进制GA的B样条重构曲线节点优化

带法向约束的自由曲线曲面重构在光学反射面设计中起至关重要的作用.本文为解决法向约束下的曲线重构问题提出了一种优化方案,使得重构出的曲线在逼近数据点的同时,亦能满足相应法向约束.首先,利用惩罚函数的方法将带法向约束的优化问题转化为无约束的优化问题.然后,引入二进制编码的遗传算法（GA）,建立合适的适应度函数,自适应产生优化节点向量,如此迭代进化,直到产生令人满意的重构曲线为止.考虑到节点向量非递减的特性,而遗传算法在寻找最优节点向量的过程中有可能打乱节点向量的顺序,所以在建立适应度函数的时候将变量调整为无序有界变量.通过与传统最小二乘方法和粒子群智能优化方法的比较,本文方案在解决带法向条件约束的曲线重构问题上优势明显,且对于任意形状的曲线重构都行之有效.     

基于改进遗传算法的船舶管路布局设计

针对船舶管路布局设计中的路径规划问题提出一种改进型遗传算法求解方法。建立船舶管路布局设计问题的模型空间、约束条件和优化目标;提出一种基于连接点网格的定长编码方法,结合该编码方法设计了适合改进遗传算法应用的适应度函数和交叉、变异算子,定长编码可降低遗传算子设计复杂度和非法个体修补代价;提出在进化流程中嵌入以“去折弯”和“改模式”两种改善型变异方法构建的爬山操作,以提升算法收敛性和寻优能力。通过仿真实验验证所提算法具有可行性和先进性。     

基于径向基网络与交互式遗传算法的服装设计

针对将交互式遗传算法应用到服装设计中产生的人的疲劳问题,提出利用神经网络来逼近适应度函数.给出了以GA操作产生的每代最佳个体初步作为神经网络径向基网络函数的中心值并结合相似距离值,利用K-Means求出径向基网络的各参数以逼近适应度函数.在服装设计系统应用中取得了良好的效果.     

Stacking sequence optimization with genetic algorithm using a two-level approximation

We propose a new method for laminate stacking sequence optimization based on a two-level approximation and genetic algorithm (GA), and establish an optimization model including continuous size variables (thicknesses of plies) and discrete variables (0/1 variables that represent the existence of each ply). To solve this problem, a first-level approximate problem is constructed using the branched multipoint approximate (BMA) function. Since mixed-variables are involved in the first-level approximate problem, a new optimization strategy is introduced. The discrete variables are optimized through the GA. When calculating the fitness of each member in the population of GA, a second-level approximate problem that can be solved by the dual method is established to obtain the optimal thicknesses corresponding to the each given ply orientation sequence. The two-level approximation genetic algorithm optimization is performed starting from a ground laminate structure, which could include relatively arbitrarily discrete set of angles. The method is first applied to cylindrical laminate design examples to demonstrate its efficiency and accuracy compared with known methods. The capacity of the optimization strategy to solve more complex problems is then demonstrated using a design example. With the presented method, the stacking sequence in analytical tools can be directly taken as design variables and no intermediate variables need be adopted.     

非下采样轮廓波域红外与可见光图像配准算法

针对灰度和对比度存在较大差异的可见光图像与红外图像的配准问题,提出了一种基于非下采样轮廓波变换的多分辨率配准方法。该方法分别对可见光图像和红外图像进行非下采样轮廓波分解,引入梯度归一化互信息作为配准图像的相似性测度,利用基于种群成熟度描述的自适应确定交叉和变异比率的改进遗传算法作为搜索策略,对高尺度低频图像进行粗配准。然后,根据粗匹配结果在低尺度低频图像上进行进一步配准,最终实现全分辨率条件下红外和可见光图像的配准。实验结果表明,提出的算法能够有效提高配准精度和速度。     

利用角度签名进行3维表面配准

3维表面的配准在3维物体重建、场景检测和物体识别过程中起着重要的作用。为此提出了一种新的3维表面表示方法——角度签名(angle signature),并将其用于3维表面配准。该表示方法将表面的局部几何信息表示成为1维的向量,具有对刚体变换的不变性。由于其简洁的表示方式,可以实现表面的快速配准。此外,该方法较其他3维表面的表示方法具有更强的鲁棒性。在实际应用中,为了提高表面配准的速度,首先筛选出特征点,然后利用特征点寻找表面之间的对应关系,从而将刚体变换的参数求出,实现表面的配准。实验结果表明,采用角度签名实现物体表面配准具有较快的速度和较高的精度。     

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

针对简单遗传算法中线性适应度函数随进化过程恒定不变的缺点。提出一种可随进化代数动态调整的非线性适应度函数。以典型的遗传算法测试函数为算例，分别以Goldberg提出的线性拉伸方法与文中提出的改进遗传算法进行计算。计算结果表明文中提出的动态适应度函数对简单遗传算法的改进有较明显的效果。     

Registering multiview range data to create 3D computer objects

Concerns the problem of range image registration for the purpose of building surface models of 3D objects. The registration task involves finding the translation and rotation parameters which properly align overlapping views of the object so as to reconstruct from these partial surfaces, an integrated surface representation of the object. The registration task is expressed as an optimization problem. We define a function which measures the quality of the alignment between the partial surfaces contained in two range images as produced by a set of motion parameters. This function computes a sum of Euclidean distances from control points on one surfaces to corresponding points on the other. The strength of this approach is in the method used to determine point correspondences. It reverses the rangefinder calibration process, resulting in equations which can be used to directly compute the location of a point in a range image corresponding to an arbitrary point in 3D space. A stochastic optimization technique, very fast simulated reannealing (VFSR), is used to minimize the cost function. Dual-view registration experiments yielded excellent results in very reasonable time. A multiview registration experiment took a long time. A complete surface model was then constructed from the integration of multiple partial views. The effectiveness with which registration of range images can be accomplished makes this method attractive for many practical applications where surface models of 3D objects must be constructed     

Feature Selection Using the Domain Relationship with Genetic Algorithms

Considering the importance of the domain relationship in eliminating noisy features in feature selection, we present an alternate approach to designing a multi-objective fitness function using multiple correlation for the genetic algorithm (GA), which is used as a search tool in the problem. Multiple correlation is a simple statistical technique that uses the multiple correlation coefficients to measure the relationship between a dependent variable and a set of independent variables within the domain space. Simulation studies were conducted on both real-world and controlled data sets to assess the performance of the proposed fitness function. The comparison between the traditional fitness function and our proposed function is also reported. The results show that the proposed fitness function can perform more satisfactorily than the traditional one in all cases considered, including different data types, multi-class and multi-dimensional data.     

Research on a face recognition system by the genetic algorithm

Computer vision and recognition is playing an increasingly important role in modern intelligent control. Object detection is the first and most important step in object recognition. Traditionally, a special object can be recognized by the template matching method, but the recognition speed has always been a problem. In this article, an improved general genetic algorithm-based face recognition system is proposed. The genetic algorithm (GA) has been considered to be a robust and global searching method. Here, the chromosomes generated by GA contain the information needed to recognize the object. The purpose of this article is to propose a practical method of face detection and recognition. Finally, the experimental results, and a comparison with the traditional template matching method, and some other considerations, are also given. This work was presented in part at the 11th International Symposium on Artificial Life and Robotics, Oita, Japan, January 23–25, 2006     

佳点集遗传算法

该文借助于遗传算法的理想浓度模型以及由此模型对遗传算法的机理的分析,给出了遗传算法的运行机理发及特点,即遗传算法是一个具有定向制导的随机搜索技术,其定向制导的原则蛎：导向以高适应度模式为祖先的“家族”方向,以此结论为基础,利用数论中的佳点休的理论和方法,对GA算法中的交叉操作进行了重新设计,给出了一个新的GA算法,称之为佳点集遗传算法,最后作者将佳点GA算法应用于求解优化问题、SAT问题、TSP问题和背包问题,并与其它求解SAT算法进行比较,通过模拟比较,可以看出新的算法不但提高了算法的速度和精度,而且避免了其它方法常有的早期收敛的现象,这说明作者对GA算法机理的理解和佳点CA算法可能为GA算法的研究开辟一条新的途径。