共查询到17条相似文献,搜索用时 171 毫秒
1.
中国邮递员问题的DNA计算 总被引:2,自引:0,他引:2
提出了“虚拟权值”和“虚拟节点”的概念, 给出了中国邮递员问题的一种基于DNA计算的求解算法。新算法首先利用多聚酶链式反应技术来排除非解, 从而得到中国邮递员问题的所有可行解; 然后,结合基于表面的DNA计算方法与荧光标记等技术, 最终从所有可行解中析出最优解。算法分析表明, 新算法具有易于解读、编码简单等特点。 相似文献
2.
基于生化反应原理的DNA计算具有强大的并行运算能力,DNA计算机在求解NP问题上存在着硅计算机无法比拟的先天的优越性。采用荧光标记的策略,给出了一种新的图的最小顶点覆盖问题的DNA表面计算模型。该模型首先将问题解空间的DNA分子固定在固体载体上,然后通过进行相应的生化反应来求得图的最小顶点覆盖问题的所有解。新算法利用荧光猝灭技术,通过观察荧光来排除非解,具有编码、解读简单和错误率低的特点。 相似文献
3.
4.
5.
6.
提出一种基于双局部最优的多目标粒子群优化算法,与可行解为优的约束处理方法相结合,来求解决非线性带约束的多目标电力系统环境经济调度问题。该算法针对传统多目标粒子群算法多样性低的局限性,通过对搜索空间的分割归类来增加帕累托最优解的多样性;并采用一种新的双局部最优来引导粒子的搜索,从而增强了算法的全局搜索能力。算法加入了可行解为优的约束处理方法对IEEE30节点六发电机电力系统环境经济负荷分配模型分别在几个不同复杂性问题的情况进行仿真测试,并与文献中的其他算法进行了比较。结果表明,改进的算法能够在保持帕累托最优解多样性的同时具有良好的收敛性能,更有效地解决电力系统环境经济调度问题。 相似文献
7.
针对有约束条件的多目标优化问题,提出了一种求解带约束的基于内分泌思想的多目标粒子群算法。利用不可行度方法和约束主导原理指导进化过程中精英种群的选择操作和约束条件的处理,根据生物体激素调节机制中促激素和释放激素间的相互作用原理,考虑当前非劣解集中的个体对其最邻近的一类群体的监督控制,引入当前粒子的类全局最优位置来反映其所属类中最好位置粒子对当前粒子的影响。为验证多目标约束优化算法的有效性,对两个典型的多目标优化问题进行了仿真实验,仿真结果表明该算法能较大概率地获得多目标约束优化问题的可行Pareto最优解。 相似文献
8.
最佳匹配问题的DNA表面计算模型 总被引:1,自引:1,他引:0
基于最佳匹配问题的问题解空间,采用荧光标记的策略,给出了一种新的最佳匹配问题的DNA表面计算模型,该模型首先将问题解空间的DNA分子固定在固体载体上,然后通过进行相应的生化反应来求得最佳匹配问题的所有解.与已有的最大匹配问题的DNA表面计算模型相比,新模型在检测边的过程中不需要使用观察法,且边的排列顺序不影响解空间的生成过程.因此,新模型具有更好的性能. 相似文献
9.
基于生化反应原理的DNA计算具有强大的并行运算能力,DNA计算机在求解NP问题上存在着硅计算机无法比拟的先天的优越性。论文采用荧光标记的策略,给出了一种新的哈密顿回路问题的DNA表面计算模型。该模型首先将问题解空间的DNA分子固定在固体载体上,然后通过进行相应的生化反应来求得哈密顿回路问题的所有解。在新模型中,解空间的生成过程与边的排列顺序无关。 相似文献
10.
列车运行调整是一类特殊的NP完全问题,由于约束众多,搜索空间庞大,可行解范围狭小,因此难以获得最优解。针对高速列车运行调整问题的特点,以智能算法中有代表性发展优势的萤火虫算法(FA)为基础,根据实际问题提出一种离散的萤火虫算法(DFA)进行求解。为了增加萤火虫群的多样性,避免算法陷入局部最优解,采用了基于变邻域搜索算法的扰动机制。将该算法用于高速列车运行调整问题,经过算例对比分析,基于离散萤火虫算法调整方案的计算结果优于普通启发式算法调整结果。 相似文献
11.
收缩背包问题是标准背包问题的一个扩展,其中背包的容量为所装物品数量的非增函数。本文提出了基于分子生物技术的求解收缩背包问题的DNA算法,首先将其约束条件进行分解;然后设计一系列与物品重量相对应的寡聚核苷酸片断及其链接模板,在链接酶的作用下将它们进行链接反应,生成代表任意物品组合的DNA链;再通过基本的生物操
作筛选出可行解;最后比较各个可行解对应的目标函数值,进而得到最优解。 相似文献
作筛选出可行解;最后比较各个可行解对应的目标函数值,进而得到最优解。 相似文献
12.
非线性规划问题的极大熵多目标粒子群算法 总被引:1,自引:0,他引:1
刘淳安 《计算机工程与设计》2008,29(4):914-916
结合非线性规划的约束条件构造了一个新的极大熵函数,利用该函数将问题转化成了两个目标的多目标优化问题.通过对违反约束动态的进行惩罚,提出了一种新的极大熵多目标粒子群算法.该方法能有效的保持群体中不可行解的一定比例,从而增加了群体的多样性,而且避免了传统的过度惩罚缺陷,使群体更好地向最优解逼近.计算机仿真表明,该算法对非线性规划问题求解是非常有效的. 相似文献
13.
The multiple destination routing (MDR) problem can be formulated as finding a minimal cost tree which contains designated source and multiple destination nodes so that certain constraints in a given communication network are satisfied. This is a typical NP-hard problem, and therefore only heuristic algorithms are of practical value. As a first step, a new genetic algorithm is developed to solve the MDR problems without constraints. It is based on the transformation of the underlying network of an MDR problem into its distance complete form, a natural chromosome representation of a minimal spanning tree (an individual), and a completely new computation of the fitness of individual. Compared with the known genetic algorithms and heuristic algorithms for the same problem, the proposed algorithm has several advantages. First, it guarantees convergence to an optimal solution with probability one. Second, not only are the resultant solutions all feasible, the solution quality is also much higher than that obtained by the other methods (indeed, in almost every case in our simulations, the algorithm can find the optimal solution of the problem). Third, the algorithm is of low computational complexity, and this can be decreased dramatically as the number of destination nodes in the problem increases. The simulation studies for the sparse and dense networks all demonstrate that the proposed algorithm is highly robust and very efficient in the sense of yielding high-quality solutions 相似文献
14.
15.
Multi-rule Multi-objective Simulated Annealing Algorithm for Straight and U Type Assembly Line Balancing Problems 总被引:5,自引:0,他引:5
Adil Baykasoglu 《Journal of Intelligent Manufacturing》2006,17(2):217-232
The task of balancing of assembly lines is of considerable industrial importance. It consists of assigning operations to workstations
in a production line in such a way that (1) no assembly precedence constraint is violated, (2) no workstations in the line
takes longer than a predefined cycle time to perform all tasks assigned to it, and (3) as few workstations as possible are
needed to perform all the tasks in the set. This paper presents a new multiple objective simulated annealing (SA) algorithm
for simple (line) and U type assembly line balancing problems with the aim of maximizing “smoothness index” and maximizing
the “line performance” (or minimizing the number of workstations). The proposed algorithm makes use of task assignment rules
in constructing feasible solutions. The proposed algorithm is tested and compared with literature test problems. The proposed
algorithm found the optimal solutions for each problem in short computational times. A detailed performance analysis of the
selected task assignment rules is also given in the paper. 相似文献
16.
This paper deals with the frame topology optimization under the frequency constraint and proposes an algorithm that solves a sequence of relaxation problems to obtain a local optimal solution with high quality. It is known that an optimal solution of this problem often has multiple eigenvalues and the feasible set is disconnected. Due to these two difficulties, conventional nonlinear programming approaches often converge to a local optimal solution that is unacceptable from a practical point of view. In this paper, we formulate the frequency constraint as a positive semidefinite constraint of a certain symmetric matrix, and then relax this constraint to make the feasible set connected. The proposed algorithm solves a sequence of the relaxation problems with gradually decreasing the relaxation parameter. The positive semidefinite constraint is treated with the logarithmic barrier function and, hence, the algorithm finds no difficulty in multiple eigenvalues of a solution. Numerical experiments show that global optimal solutions, or at least local optimal solutions with high qualities, can be obtained with the proposed algorithm. 相似文献
17.
We propose a new method for solving transportation problems based on decomposing the original problem into a number of two-dimensional
optimization problems. Since the solution procedure is integer-valued and monotonic in the objective function, the required
computation is finite. As a result, we get not only a single optimal solution of the original transportation problem but a
system of constraints that can yield all optimal solutions. We give numerical examples that illustrate the constructions of
our algorithm. 相似文献