基于免疫机制和遗传算法的网络k-划分优化

计算机网络k-划分优化是对网络进行控制管理的有效方法之一。该文给出了一种基于免疫机制和遗传进化的计算机网络k-划分优化算法。该算法在遗传算法中引入免疫机制，有效克服了标准遗传算法的“早熟”现象，提高了算法的搜索效率；同时，采用一种新的杂交、变异算子，更便于算法的硬件实现。理论分析和仿真实验表明该算法是非常有效的。     

一种改进的计算机网络k-划分优化遗传算法

本文运用无向图多划分优化的方法研究计算机网络k-划分优化问题，结合问题本身的特点，设计了一种启发式遗传算法，从适应度函数设计，遗传操作算子以及参数选取等方面对经典遗传算法进行了改进，实验研究验证了算法的正确性和高效性。     

一种通用的求解图的多划分问题的改进遗传算法

针对图的多划分问题的特点,本文提出了一种适合于求解这一类问题的改进遗传算法,该算法无论在编码方式,算子设计及至算子功能的界定上,都经经典遗传算法有着很大差别,实例验证,该算法是通用和有效的。它既充分利用了遗传算法全局性的搜索能力,又增加了跗算法的局部搜索能力,明显地提高了收敛速度,该算法的提出,大大减轻了用户解决具体应用问题的负担。     

MSNV:基于多层次社团划分的网络结构可视化方法

针对大规模网络节点数目庞大、结构复杂性高,有限的屏幕空间难以展示其结构特征的问题,提出了一种基于社团划分的多层次网络可视化方法。首先,使用基于网络模块度的社团划分算法对网络节点进行划分,并采用贪婪算法寻找最大模块度的社团划分,得到不同层次粒度的社团;其次,通过设置层次约束力以改进经典力导引算法(FDA),使改进的算法能对不同层次粒度的社团实现分层布局,解决FDA无法展示网络节点层次性的问题;最后,使用多窗口视图、Overview+Detail等交互方法分别展示高层社团和底层节点,实现兼顾网络高层次宏观结构和低层次局部细节的显示。仿真实验中,该算法的社团划分相较于自包含GN算法在效率和准确率上有所提高。案例分析表明,所提方法在大规模网络结构的显示和交互方面具有良好的效果和性能。     

改进模拟退火算法在模块划分中的研究及应用

模块划分是产品模块化设计的关键技术之一。目前大多采用非数值方法划分模块，数值划分方法主要是使用模拟退火算法或遗传算法。模拟退火算法虽可以一次性得到模块划分最优方案，但是操作困难，效率不高。而遗传算法容易陷入局部最优解。该文在模拟退火算法的基础上，融入遗传算法的种群思想，提出了基于改进模拟退火算法的模块划分方法，研究了其实现的关键技术，并通过VC++6.0将其实现。通过具体的模块划分实例，证实了该方法的高效性和易操作性。     

基于组合算法的嵌入式系统软硬件划分方法

嵌入式系统软硬件划分是一个多约束条件、多目标的组合优化问题,单一算法难以找到最优设计方案,为此,提出一种遗传算法和粒子群算法组合的嵌入式系统软硬件划分方法。首先建立嵌入式系统软硬件划分问题的数学模型,然后利用遗传算法找到问题的可行解,最后采用粒子群算法找到最优方案,并采用仿真实验测试算法的性能。仿真结果表明,该方法提高了嵌入式系统软硬件划分问题的求解效率,可以快速找到更优的软硬件划分方案。     

自动区域划分的分区域搜索狭义遗传算法

用数学方法难以解决函数优化中的区域划分问题．为此,提出了用狭义遗传算法实现区域划分的方法．实现了基于自动区域划分的分区域搜索的狭义遗传算法,阐述了分区域搜索的控制策略。从理论上分析了基于自动区域划分的区域搜索的狭义遗传算法是全局收敛的,并具有收敛速度快、搜索过程稳定性高、可控制性强、便于并行实现等特点．最衙提出了有待研究的问题。     

基于度系数的社团分裂算法

复杂网络社团划分中的分裂算法是比较经典的算法,本文通过引入度系数这一局部变量,通过运用kruksal算法对经典的GN算法进行适当改进,提高了搜索效率,并通过对其模块度特征的分析,表明了结果的准确性。     

基于改进遗传算法的可重构计算任务划分

为实现可重构计算中的软硬件任务自动划分,引入了遗传算法来搜寻最优解。为解决标准遗传算法可能出现种群早熟和种群进化后期收敛速度慢的问题,使用了小生境技术来保护种群中基因的多样性。设计了能够随适应度自动改变的自适应遗传算子（杂交算子和变异算子）。对算法进行了50次随机实验,并对结果进行分析。实验表明,改进后的遗传算法搜寻到全局最优任务划分的概率和搜寻到最优任务划分时的进化代数都要优于标准遗传算法。     

UPSO:基于划分空间粒子群优化的WSN动态覆盖优化算法

针对WSN动态覆盖问题为多目标优化问题,提出一种划分空间粒子群优化动态覆盖算法UPSO(Uniform Particle Swarm Optimization,UPSO)。该算法首先定义出基于传感器平均分布和不平均分布的区域划分过程,然后分别在不同子空间利用粒子群进行子区域内搜索Pareto最优解,最后分析算法复杂度。实验表明,在不同网络规模、迭代次数和划分子空间下,区域覆盖度和网络寿命相对于传统经典算法有较好改进。     

基于遗传算法的集合划分问题求解

集合划分问题是组合优化领域中有着广泛应用基础的著名问题,属于NP难问题.通过引入精英策略提出对遗传算法的改进,并为了能把遗传算法应用到集合划分问题,对数学模型进行了等价变换.针对集合划分问题,设计出一种高效的基因表示,避免了组合优化中处理约束条件的麻烦.解决了传统二进制基因编码无法精确适应离散优化问题,首次提出一种离散编码解决方案.最后,使用Visual C 6编程实现,取得较好的结果.     

电路划分问题的算法研究与计算机实现

在介绍电路划分问题的基础上，提出了一种基于宏单元的电路划分数学模型，同时给出了利用计算机解决该问题的遗传算法的设计和实现过程。将该实现方案用于对标杆电路划分进行测试，与传统的F-M划分算法相比，划分结果得到明显改善。     

拉丁超立方体抽样遗传算法求解图的二划分问题

图的二划分问题是一个典型的NP-hard组合优化问题, 在许多领域都有重要应用. 近年来, 传统遗传算法等各种智能优化方法被引入到该问题的求解中来, 但效果不理想. 基于理想浓度模型的机理分析, 利用拉丁超立方体抽样的理论和方法, 对遗传算法中的交叉操作进行了重新设计, 并在分析图二划分问题特点的基础上, 结合局部搜索策略, 给出了一个解决图二划分问题的新的遗传算法, 称之为拉丁超立方体抽样遗传算法. 通过将该算法与简单遗传算法和佳点集遗传算法进行求解图二划分问题的仿真模拟比较, 可以看出新的算法提高了求解的质量、速度和精度.     

Annealing-based heuristics and genetic algorithms for circuit partitioning in parallel test generation

In this paper simulated annealing and genetic algorithms are applied to the graph partitioning problem. These techniques mimic processes in statistical mechanics and biology, respectively, and are the most popular meta-heuristics or general-purpose optimization strategies. A hybrid algorithm for circuit partitioning, which uses tabu search to improve the simulated annealing meta-heuristics, is also proposed and compared with pure tabu search and simulated annealing algorithms, and also with a genetic algorithm. The solutions obtained are compared and evaluated by including the hybrid partitioning algorithm in a parallel test generator which is used to determine the test patterns for the circuits of the frequently used ISCAS benchmark set.     

基于顶点组重分配的动态增量图划分算法

图划分是分布式图计算中的一项基础工作, 其作用是将大规模图进行划分并分配到集群中的不同机器上. 图划分的质量对分布式图计算的性能有很大的影响, 其目标是降低负载平衡和最小化边割. 如今, 现实中的图数据通常呈动态增长态势, 这就需要一种能够处理动态增量图的划分方法, 在图数据动态增长的过程中确保划分的质量不受影响. 目前虽然有一些动态图划分算法被提出, 但它们不能同时专注于实时处理动态变化和获得高质量的划分结果. 提出基于顶点组重分配的动态增量图划分算法(ED-IDGP)来解决大规模动态增量图的划分问题. 在ED-IDGP算法中, 设计实时处理4种不同单元更新类型的动态处理器, 并在每次处理完单元更新后通过在分区发生动态变化的附近执行局部优化器进一步提高图划分的质量. 在ED-IDGP的局部优化器中, 利用基于改进标签传播算法的顶点组搜索策略搜索顶点组, 并利用提出的顶点组移动增益公式衡量最有益的顶点组, 将该顶点组移动到目标分区中做优化. 在真实数据集上从不同的角度和度量指标评估了ED-IDGP算法的性能和效率.     

A hybrid multi-objective PSO algorithm with local search strategy for VLSI partitioning

Very large scale integration (VLSI) circuit partitioning is an important problem in design automation of VLSI chips and multichip systems; it is an NP-hard combinational optimization problem. In this paper, an effective hybrid multi-objective partitioning algorithm, based on discrete particle swarm optimzation (DPSO) with local search strategy, called MDPSO-LS, is presented to solve the VLSI twoway partitioning with simultaneous cutsize and circuit delay minimization. Inspired by the physics of genetic algorithm, uniform crossover and random two-point exchange operators are designed to avoid the case of generating infeasible solutions. Furthermore, the phenotype sharing function of the objective space is applied to circuit partitioning to obtain a better approximation of a true Pareto front, and the theorem of Markov chains is used to prove global convergence. To improve the ability of local exploration, Fiduccia-Matteyses (FM) strategy is also applied to further improve the cutsize of each particle, and a local search strategy for improving circuit delay objective is also designed. Experiments on ISCAS89 benchmark circuits show that the proposed algorithm is efficient.     

OPAL: A new algorithm for optimal partitioning and learning in non parametric unsupervised environments

A nonlinear programming approach to the problem of learning in nonparametric and unsupervised environments is put forth in this study. The approach exploits the concept of optimal partitioning of the given data set as the objective of such nonparametric unsupervised learning. This partitioning or clustering is achieved by the application of the recently developed improved flexible polyhedron method (IFPM) to the associated optimization problem. The optimization problem is defined here in terms of a new, conceptually innovative optimality criterion based on intergroup and intragroup distinct scatters. Details of this new approach, a procedure for deriving an initial partition, and application of the algorithm to two numerical examples are presented.     

求解VLSI 电路划分问题的混合粒子群优化算法

电路划分是VLSI物理设计过程中的一个关键阶段.该问题本质上是一个NP困难的组合优化问题.针对该问题,提出了一种带FM策略的混合粒子群优化算法.引入遗传算法的两点交叉算子和随机两点交换变异算子,保证了粒子在位置更新后依然可行;为了提高算法的局部搜索能力,将具有较强局部搜索能力的FM策略融入算法的位置更新;设计了种群多样性变异策略,提高了种群多样性,避免了易陷入局部最优的缺陷.对ISCAS89标准测试电路的仿真实验结果表明,所构造的算法是有效的.     

基于遗传粒子群优化的嵌入式系统软硬件划分算法

针对单处理器嵌入式系统软硬件划分问题,采用带权有向无环图进行建模,并将之约简,进而转换为多约束条件的0/1背包问题求解.由于基本粒子群优化算法无法求解0/1背包问题,故将遗传算法中的交叉、变异思想引入粒子群优化算法,提出了求解离散组合优化问题的遗传粒子群优化(GPSO)算法,采用两点交叉算子和非均匀变异算子对粒子的位置和速度更新方法进行了重新定义.实验结果表明,采用文中算法能有效地解决软硬件划分问题,具有良好的全局搜索能力,其寻优能力和执行时间优于遗传算法和模拟退火算法.