共查询到18条相似文献,搜索用时 620 毫秒
1.
提出了一种基于遗传算法的新的平面图画图算法,算法将平面图画图问题转化为约束优化问题,用遗传算法求解目标函数的最优解的近似值,从而得到平面图的平面直线画法.新算法的优点是:方法简单,易于实现,画出的图形美观.实验结果表明:算法画出的图形要比文献[8]中的算法画出的图形美观,而其收敛性则要高于标准遗传算法. 相似文献
2.
3.
采用不可微精确罚函数的约束优化演化算法 总被引:5,自引:0,他引:5
针对多数已有的采用罚函数的约束优化遗传算法存在优化效果差的问题 ,提出了一种新的求解约束优化问题的演化算法 .借助不可微精确罚函数把约束问题转化为单个无约束问题来处理 .采用混合杂交和间歇变异来提高算法的搜索能力 .数值实验结果表明了新算法的优化效果远远优于已有的几种采用罚函数的遗传算法 相似文献
4.
邓卫民 《计算机与数字工程》2013,41(8)
针对多约束QoS组播路由的优化问题,提出了一种超混沌遗传混沌算法.该算法利用遗传算法中的改进的适应度函数,通过结合超混沌映射优越性的搜索能力,对遗传算法选出的个体进行混沌优化,以改善遗传算法过早陷入早熟的情况.通过仿真实验表明,该算法有效地改进了搜索效率,且收敛速度更快更稳定,是一种解决多约束QoS路由问题可行和有效的方法. 相似文献
5.
汪民乐 《计算技术与自动化》2003,22(2):5-7,109
文章针对一般约束多目标优化问题,在设计了新的适应度函数和选择算子的基础上,提出一种新型多目标遗传算法。将其应用于集群目标靶场效能优化问题,验证了算法的有效性。 相似文献
6.
7.
对带宽、延时、延时抖动约束最小代价的QoS组播路由问题进行了研究,提出一种基于量子行为微粒群优化(QPSO)算法来设计路由优化算法。该算法采用一种节点序列编码方案,将路由优化问题转化成一种准连续优化问题,并采用罚函数处理约束条件。应用QPSO算法求解QoS组播路由问题的算例,并与遗传算法和改进后的遗传算法进行比较。计算机仿真实验证明,该算法可以更有效地求得QoS组播路由问题的优化解,可靠性较高。 相似文献
8.
9.
针对边值固定动态优化问题的数值求解,提出了一种集成随机性方法与确定性方法的一种新的混合算法。迭代遗传算法(IGA)把初始种群及繁衍产生的后代不断供给两点梯度法,两点梯度法以其为初值搜索满足边值固定约束的可行控制策略并回送给迭代遗传算法,迭代遗传算法则根据可行控制策略对应的目标函数值进行选择与进化操作。该混合算法简便易行。实例研究显示了该混合算法的可行性与稳健性,能以足够的精度满足边值约束。 相似文献
10.
在研究了现有画有向无环图的主要方法的基础上提出一种基于遗传算法的有向无环图画图算法,将一般有向无环图的画图问题转换为函数优化问题,用遗传算法求目标函数最优解的近似值。实验表明此算法具有算法统一、方法简单、容易实现、易于修改,并且具有自适应、自学习和易于并行化的特点。 相似文献
11.
Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs. 相似文献
12.
13.
《国际计算机数学杂志》2012,89(14):3138-3148
Most of graph drawing algorithms draw graphs on unbounded planes. However, there are applications that require graphs to be drawn on the plane inside a given polygon. In this paper, a new algorithm for planar orthogonal drawing of complete binary trees inside rectilinear polygons is presented. Uniform distribution of nodes of graphs on drawing regions is one of the aesthetics criteria in graph drawing. The goal of this paper is to produce planar orthogonal drawings with a relatively uniform node distribution and few edge bends. The proposed algorithm can be considered as a generalization of the H-tree layout method for rectilinear polygons. A new linear time algorithm is also given for bisecting rectilinear polygons into two equi-area rectilinear sub-polygons. 相似文献
14.
Bernadete M.M. NetaAuthor Vitae Gustavo H.D. AraújoAuthor Vitae 《Applied Soft Computing》2012,12(4):1379-1389
This paper reflects results of research related to developing a new methodology for automatic graph drawing based on applying genetic algorithms. The methodology has permitted the elaboration of a hybrid technique that combines the most popular, classical, topology-shape-metric approach to orthogonal drawings on the grid and a genetic algorithm that is directed, in its evolutionary process, at multicriteria decision making in a fuzzy environment. In the traditional use of the topology-shape-metric approach, a single fixed planar embedding is obtained in the planarization step. Thereafter this embedding is subjected to the orthogonalization and compaction steps. However, this sequence does not guarantee that the fixed planar embedding will generate a final drawing of a good quality. Moreover, every topology-shape-metric step is classified as a NP-hard problem, and choices as well as heuristics used in previous stages have a direct impact on subsequent ones. Taking this into account, the developed hybrid technique generates a greater number of planar embeddings by varying the order of edges’ insertion when forming the planar embeddings in planarization step. Thus, the problem is formulated as a permutation-based combinatorial optimization problem. The genetic algorithm is applied at the planarization step of the topology-shape-metric. This allows one to generate the population with the corresponding number of planar embeddings. Each planar embedding obtained in the planarization step is submitted to the orthogonalization and compaction. Their results serve for applying the procedures of multicriteria decision making in a fuzzy environment. Thus, in the evolutionary process, the genetic algorithm is able to select individuals, which provide more harmonious solutions (relatively of the solutions obtained with traditional applying the topology-shape-metric approach) from the point of view of the aesthetic criteria that are usually utilized at the three steps of automatic graph drawing. This is convincingly demonstrated by experimental results given in the paper. 相似文献
15.
16.
Simultaneous representations of planar graphs and their duals normally require that the dual vertices to be placed inside their corresponding primal faces, and the edges of the dual graph to cross only their corresponding primal edges. Erten and Kobourov [C. Erten, S.G. Kobourov, Simultaneous embedding of a planar graph and its dual on the grid, Theory Computer Systems 38 (2005) 313-327] provided a linear time algorithm on simultaneous straight-line grid embedding of a 3-connected planar graph and its dual such that all the vertices are placed on grid points and each edge is drawn as one straight-line segment except for one which is drawn using two segments. Their drawing size is (2n−2)×(2n−2), where n is the total number of vertices in the graph and its dual. They raised an open question on whether there is a large class of planar graphs that allows this simultaneous straight-line grid embedding on a smaller grid. We answer this open question by giving a linear time simultaneous straight-line grid embedding algorithm for a 3-connected planar graph and its dual on a grid of size (n−1)×n. 相似文献
17.
A star-shaped drawing of a graph is a straight-line drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. In this paper, we consider the problem of finding a star-shaped drawing of a biconnected planar graph with the minimum number of concave corners. We first show new structural properties of planar graphs to derive a lower bound on the number of concave corners. Based on the lower bound, we prove that the problem can be solved in linear time by presenting a linear-time algorithm for finding a best plane embedding of a biconnected planar graph with the minimum number of concave corners. This is in spite of the fact that a biconnected planar graph may have an exponential number of different plane embeddings. 相似文献