多目标遗传算法中文

一种在复杂网络中发现社区的多目标遗传算法

Clara Pizzuti

摘要——本文提出了一种揭示复杂网络社区结构的多目标遗传算法。该算法优化了两个目标函数，这些函数能够识别出组内节点密集连接，而组间连接稀疏。该方法能产生一系列不同等级的网络社区，其中解的等级越高，由更多的社区组成，被包含在社区较少的解中。社区的数量是通过目标函数更佳的折衷值自动确定的。对合成和真实网络的实验，结果表明算法成功地检测到了网络结构，并且能与最先进的方法相比较。

关键词：复杂网络，多目标聚类，多目标进化算法

1、简介

复杂网络构成了表示组成许多真实世界系统的对象之间关系的有效形式。协作网络、因特网、万维网、生物网络、通信传输网络，社交网络只是一些例子。将网络建模为图，节点代表个体，边代表这些个体之间的联系。

复杂网络研究中的一个重要问题是社区结构[25]的检测，也被称作为聚类[21]，即将一个网络划分为节点组，称作社区或簇或模块，组内连接紧密，组间连接稀疏。这个问题，如[21]指出，只有在建模网络的图是稀疏的时候才有意义，即边的数量远低于可能的边数，否则就类似于数据簇[31]。图的聚类不同于数据聚类，因为图中的簇是基于边的密度，而在数据聚类中，它们是与距离或相似度量紧密相关的组点。然而，网络中社区的概念并未严格定义，因为它的定义受应用领域的影响。因此，直观的理解是同一社区内部边的数量应该远多于连接图中剩余节点的边的数量，这构成了社区定义的一般建议。这个直观定义追求两个不同的目标：最大化内部连接和最小化外部连接。

多目标优化是一种解决问题的技术，当多个相互冲突的目标被优化时，成功地找到一组解。通过利用帕累托最优理论[15]获得这些解，构成了尽可能满足所有目标的全局最优解。解决多目标优化问题的进化算法取得成功，是因为它们基于种群的特性，同时产生多个最优解和一个帕累托前沿[5]的优良近似。

因此，社区检测能够被表述为多目标优化问题，并且帕累托最优性的框架可以提供一组解对应于目标之间的最佳妥协以达到最优化。事实上，在上述两个目标之间有一个折衷，因为当整个网络社区结构的外部连接数量为空时，那它就是最小的，然而簇密度不够高。

在过去的几年里，已经提出了许多方法采用多目标技术进行数据聚类。这些方法大部分在度量空间[14], [17],[18], [28], [38], [39], [49], [51]聚集目标，虽然[8]中给出了分割图的一个方法，并且在[12]中描述了网络用户会议的一个图聚类算法。

本文中，一个多目标方法，名为用于网络的多目标遗传算法(MOGA-Net)，通过利用提出的遗传算法发现网络中的社区。该方法优化了[32]和[44]中介绍的两个目标函数，它们已被证实在检测复杂网络中模块的有效性。第一个目标函数利用了community score的概念来衡量对一个网络进行社区划分的质量。community score值越高，聚类密度越高。第二个目标函数定义了模块中节点fitness的概念，并且反复迭代找到节点fitness总和最大的模块，以下将这个目标函数称为community fitness。当总和达到最大时，外部连接是最小。两个目标函数都有一个正实数参数控制社区的规模。参数值越大，找到的社区规模越小。MOGA-Net利用这两个函数的优点，通过有选择地探索搜寻空间获得网络中存在的社区，而不需要提前知道确切的社区数目。这个数目是通过两个目标之间的最佳折衷自动确定的。

多目标方法的一个有趣结果是它提供的不是一个单独的网络划分，而是一组解。这些解中的每一个都对应两个目标之间不同的折衷，并对应多种网络划分方式，即由许多不同簇组成。对合成网络和真实网络的实验表明，这一系列帕累托最优解揭示了网络的分层结构，其中簇的数目较多的解包含在社区数目较少的解中。多目标方法的这个特性提供了一个很好的机会分析不同层级

的网络和研究不同模块化水平的社区。

本文组织如下，在下一节定义社区的概念，规范化社区检测问题。第三节描述社区检测的主要方法。第四节将社区检测问题公式化为一个多目标优化问题。第五节描述了该方法，采用基因表示，变异操作的使用。第六节给出该方法用于合成网络和真实网络的结果，以及与一些最先进方法的对比。最后，在第七节讨论多目标方法的优点，得出结论。

2、社区定义

一个网络N 能被模型化为一个图G=(V,E)，其中V 是一系列客体，被称作节点或顶点，E 是一系列连接，被称作边，这是连接了V 中的两个元素。网络中的一个社区（也被称作簇或模块）是一组相互连接密度较高的顶点（即一个子图），并且组与组之间连接密度较低。社区的这个定义相当模糊，并且在密度这个概念上没有达成一致。[48]中介绍了一个更为正式的定义，通过考量一个一般的节点i 的度k i ，定义ij

j i A k ∑=，这里A 是G 的邻接矩阵。如果节点i 到节点j 之间有一条边，那么矩阵A 的（i ，j ）位置上为1，否则为0。假设G S ?，节点i 属于G 的子图S ，i 的度分成两部分，

)()()(S k S k S k out i in i i +=

这里，∑∈=S j ij in i A S k )(，是i 与S 中其他节点相连的边的数量。∑?=S

j ij out i A k ，是i 与网络其余

部分节点相连的边的数量。如果S i S k S k out i in i ∈?>),()(，则子图S 称为强社团。如果∑∑∈∈>S i S

i out i in i S k S k

)()(，则子图S 称为弱社团。 因此，在一个强社区中，每个节点在社区内与图中剩余部分相比，连接更多。在一个弱社区中，子图内节点内度的总和大于节点外度的总和。接下来，我们采用弱社区的概念，因此一个社区被看作一系列节点，它们的内部连接的数量高于不同簇之间外部连接的数量。

3、相关工作

来自不同领域例如物理学，统计学，数据挖掘，进化计算的许多不同算法已经被提出用来检测复杂网络中社区。被采用的这些方法可以被概括地归为三类：分层分裂方法，分层凝聚方法

[31]，以及优化方法。分层分裂方法从完整的网络开始，检测连接不同社区的边，并移除它们。这些方法的例子可以在[3],[25],[35],[41],[42]和[48]。分层凝聚方法将每个节点看成一个社区，然后递归地合并相同的社区，直到得到整个图[4],[34],[40],[45],[47],[58]。优化方法定义了一个目标函数将图划分为子图，并且尝试将这个目标最大化从而获得网络的最佳分割

[1],[32],[53]。在这些优化方法中，有几种方法通过利用进化技术已经成熟。尤其

[18],[20],[26],[29],[34],[44],[55]运用了遗传算法。许多其他的方法利用多目标进化算法在度量空间来分割图或者聚集对象[8], [12],[14], [17], [28], [38], [39], [49], [51]。

接下来，我们首先回顾一下来自物理和数据挖掘领域的主要建议，然后报告一个多目标进化聚类方法的描述。

A.复杂网络的社区检测

一些研究人员研究了社区检测问题，最先进建议的完整描述已经超出了本文的范围。复杂网络社区识别方法广泛而详细的概述可以在[6],[21],[23]中找到。检测社区最著名的算法是由Newman 和Girvan[25]提出的。该方法通过删除边来反复地分裂网络。通过利用中间性的测量来选择被移除的边。以边的中间性为基础的想法来源于观察到的：如果两个社区通过几条社区间的边连接，那么从一个社区的顶点到另一个社区的顶点的所有路径，必须要通过这些边。路径决定了计算边所得的中间性分值，通过计算穿过每条边的所有路径，并且删除得分值最高的边，网络

内部的连接被破坏。重复这个过程，并且将网络划分为更小的部分，直到没有边剩余。

同一作者[42]提出了一个基于不同的中间性测量值的分层分裂方法。在这篇文章中，Newman 和Girvan 指出需要通过一个算法得出网络划分质量的测量值。出于这个目的，他们引入了模块度的概念。通俗地讲，模块度就是如果不考虑社区结构而边随机，社区内边的比例与边比例的期望值之差（模块度的正式定义是在下一节中）。数值接近1表明社区结构明显。因此，该算法计算某网络的每个分立社区的模块度，并且作者表明，当社团结构先验已知，高数值的模块度密切对应预期的网络划分。

Newman[40]认为因为高数值的模块度对应好的网络划分，找到网络可能最佳划分的方法就是优化它。因此，他提出一个分层凝聚方法用于搜寻模块度的最优值。Newman 注意到，彻底搜寻所有可能的划分方式以获得模块度的最优值，对于由超过20个顶点构成的复杂网络来说是难以实现的，因此需要近似方法。他提出一个贪婪方法，连接社区使得模块度值产生最大增值。基于相同策略的一个更快的方法在[4]中由Clauset ，Newman 和Moore 描述。

Blondel et al .[3]提出了一个方法划分大型网络，也是基于模块度优化。该算法由两个阶段组成，反复迭代，直到没有得到进一步改善。起初，网络中的每个节点都认为是一个社区。然后，对每个节点i ，考虑它所有相邻的节点j ，并且计算将i 从它所在的社区移除以及将它增加到j 所在的社区后的模块度增益。将节点放置在增益为正且最大时的社区中。如果没有社区有正的增益，i 保留在它原来的分组中。重复第一阶段直到没有节点可以移动来改善模块度。第二阶段建立一个网络，其中已有的社区当作一个新的节点，如果有一条边在属于a 社区的节点和属于b 社区的节点之间，那么在ab 两个社区之间有连接。新的社区能够被加权，在这种情况下，ab 之间边的重量就是相应社区节点之间的连接的权重之和。在这一点上，可以重复该方法，直到无法做更多的改变以提高模块度。算法返回所有发现的不同等级的聚类。

Pons 和Latapy [45]介绍了一个名为Walktrap 的分层凝聚算法，用于计算网络的社区结构。该方法是基于图的随机游动，并且认为随机游动倾向于困在图中密集连接的部分。两个节点之间距离的新定义是利用随机游动的性能引入的，并且这个定义可以推广到计算两个社区之间的距离。算法从图的划分开始，其中每个节点是一个社区，然后合并两个相邻的社区（即至少有一个公共边），将两个顶点之间距离的平方值的均值以及它的社区最小化。重新计算社区之间的距离，重复先前的步骤，直到所有的节点属于同一社区。为了选出最佳划分，采用Newman 和Girvan 的模块度标准。

Pujol et al .[47]提出一个分层凝聚算法，将光谱分析和模块度优化结合获得网络社区识别的效率和准确度。他们利用Pons 和Latapy [45]所采用的随机游动的相同概念产生网络的初始分区，然后运用分层凝聚方法反复连接两个社区。为了合并两个簇，对总模块度贡献最少的节点群被选出，把它与能将模块度增值最大的节点群连接。

Lancichinetti et al .[32]基于社区S 的community fitness 概念，提出一个方法来检测重

叠和分层的社区结构。设)(S k in i 和

)(S k out i 是社区S 中节点的内度和外度。S 的community fitness Ρ(S)定义如下：

α

))()(()()(S k S k S k S out i

in i in i S i +∑=P ∈ 其中α是分辨率参数，是一个正实数参数，控制社区的规模。当

i S k out i ?=,0)(时，对固定的α，Ρ(S)达到它的最大值。[32]中使用community fitness 以每次一个找出了所有社区。作者介绍了关于社区S 的node fitness 的概念，作为有和没有节点i ，S 的community fitness 的变化，即

}){(}){()(i S i S S i -P -?P =P

该方法首先随机选择一个节点,并考虑它作为一个社区。然后遍历S 的所有相邻节点但不包含在S 中，选择相邻节点增加到S 中。通过计算每个节点的node fitness 做出选择，并且将fitness 值最高的节点增加到S 中。此时重新计算每个节点的fitness ，并且将fitness 为负值的节点从S 中移除。当S 中节点的所有不包含的相邻节点fitness 值为负。一旦得到一个社区，选择一个新的节点，重新开始这个过程，直到所有的节点被指派给至少一组。作者发现得到的划分与分辨率参数α=1是相关的。然而，他们引入了一个基于稳定性概念的标准进行选择划分。如果对于一个取值范围内的α都能实现，则认为这种划分是稳定的。这个范围的长度决定了划分的更稳定，这就是最佳的结果。

B.多目标聚类方法

多目标优化聚类数据的应用程序近来引起人们的极大兴趣[14][17][28][38][39][49][51]尽管关于网络划分的建议很少[8][12]。

用于数值和分类数据的多目标聚类算法的参考方法是由Handl 和Knowles [28]提出的，并且将之命名为multiobjective clustering with automatic K-determination (MOCK)。MOCK 的第一目标是最小化一个划分的整体偏差，即数据项之间总的距离和已经被分配的簇的中心。第二个目标是最小化簇的连通性，计算每个簇数据点有多少个最近的邻点被放在相同的簇中。算法采用Park 和Song [43]提出的基于轨迹的邻接，这在下一节中描述，并被MOGA-Net 采用了，而且使用了基于最小生长树的特殊初始解，减少了执行时间。MOCK 也包含了从帕累托前沿近似中选择最优解的最后一步，能够自动实现最优数量的簇。

MOCK 不是专门用于网络划分的，尽管它被用于图的聚类，通过考虑网络的邻接矩阵作为（非）相似矩阵。

Datta et al. [8]提出了优化三个不同的目标用于划分图。目标将边缘值中的净亏损最小化，当两个连接的节点处于不同的社区时，社区在规模以及簇传播上有不同。作者强调了图中区域的概念，意为相邻节点的团体。因此，染色体是节点的集合，其中每个节点根据它在图中的位置是确定的。算法能将图划分为数量可变的区域，然而区域的范围和每个区域的节点数作为输入参数必须固定。

最近，一个专门用于分类网络用户会议的多目标进化算法由Nildem et al. [12]提出。获得的簇被用于网络推荐系统用于表示使用模式。用户访问的web 页面序列被表示为一个加权无向图，其中每个序列都是一个节点，连接两个边的序列的权重是两个节点之间计算得到的相似性。他们的算法名为GraSC ，使用和MOCK 相同的表示法，但待优化的冲突目标是最小-最大削减[13]和轮廓指数[50]。前者试图优化社区内之间的相似性并减小子图之间的相似性，后者计算属于同一社区的顶点的平均轮廓指数。节点i 的轮廓指数是两个平均非相似性之间的归一化值：节点i 与其它社区的节点之间的最小平均非相似性，节点i 和同一社区的其他顶点之间的平均非相似性。

在下一节，社区检测问题被形式化为一个多目标优化问题。

4、作为多目标优化问题的社区检测

不同领域的许多问题都自然地通过多个目标表述出来。特别地，将一个网络划分为组内连接紧密，组间连接稀疏的节点群有两个相互矛盾的目标。第一个目标是将属于同一个社区的节点间连接最大化，第二个目标是将社区之间的连接数量最小化。因此，社区检测问题不能够被充分地表示为一个单一目标，增加了暗中满足其他目标的限制。更合适的方法是将这个问题正式化为一个多目标聚类问题[19][28]。

一个多目标聚类问题（Ω,F1, F2, . . . , Ft ）定义如下：

t i S F i ,...,1),(min = 服从Ω∈S

其中Ω={S1,...,Sk}是网络的一系列可能社区。F = {F1, F2, . . . , Ft}是一组单标准函数。每一个Fi:Ω→R 是不同的目标函数，这些函数决定了得到的社区的可行性。因为F 是一个将这些相互矛盾的目标必须同时优化的向量，这个问题没有唯一解，但是通过利用帕累托最优理论[15]可以找到一系列解。考虑两个解S1和S2∈Ω，解S1支配解S2，记为S1 ?S2，当且仅当

)(S F < )(S F : i ∧ )(S F ≤ )(S F : i 2i 1i 2i 1i ??

一个支配解并不会引人注意，因为对所有的目标都可以进一步改善。相反，一个非支配解想要在某一个目标上改善就要牺牲另一个目标。多目标优化的目的就是生成和选择非支配解，这些解被称为帕累托最优。因此目标是构建帕累托最佳状态。更正式地讲，一系列帕累托最优解Π被定义为

: ∈ {S = Ω∏不存在Ω∈'S 且S ’?S}

向量F 将解空间映射到目标函数空间。当非支配解标注在目标空间中，它们被称作帕累托前沿。因此帕累托前沿代表了更佳的折衷，尽可能满足所有目标的解。值得注意的是，正如[28]中所概述的，帕累托最优解总是包含优化单目标的聚类问题的最优解。

A.目标函数

我们的目标是将网络划分成一组组{S1,...,Sk}的顶点，在这些组里边的密度比组间边的密度高。为此，我们需要一个目标函数能够最大化每个社区内部连接的数量，以及另一个目标函数最小化社区之间连接的数量。

[44]中介绍了衡量一个社区S 质量，最大化S 中节点的入度。另一方面，[32]中定义了一个标准，最小化一个社区的出度。两种方法都采用了上述弱社区的定义。首先我们回忆一下这些措施的定义，然后展示它们如何利用多目标方法找到找到社区的。接下来，不失一般性，将网络假设为无向图进行建模。

假设μi 表示连接节点i 的边与社区S 中其他节点的边的比值。更正式地为

)(||1S k S in i i =

μ 这里|S|是社区S 的基数。

社区S 的r 阶幂平均值记作M(S)，定义为

|

|)()(S S M r

i S i ∑∈=μ 注意，M(S)的计算中，因为0≤μ≤1，指数r 增加了与属于同一社区的其它节点连接很多的节点的权重，减小了在S 中连接较少的那些点的权重。

社区S 的体积νS 定义为社区内部节点的边的总数，即与S 相对应的邻接矩阵中1的数量

∑∈=

S j i ij S A ,υ

社区S 的score 定义为score(S)=M(S)×νS 。因此，score 将节点间连接比例（通过幂平均值）和社区S 包含的内部连接的数量（通过体积）都考虑了。网络的一种社区划分{S1,...,Sk}的community score 定义为

∑==k i i S score CS 1)

(

第一个目标是最大化社区得分（community score ）CS 。 正如第三节所述，Lancichinetti et al. [32]介绍了社区S 的community fitness 概念

α

))()(()()(S k S k S k S out i in i in i S i +∑=P ∈

遗传算法在多目标优化的应用：公式,讨论,概述总括

遗传算法在多目标优化的应用：公式，讨论，概述/总括 概述 本文主要以适合度函数为基础的分配方法来阐述多目标遗传算法。传统的群落形成方法（niche formation method）在此也有适当的延伸,并提供了群落大小界定的理论根据。适合度分配方法可将外部决策者直接纳入问题研究范围，最终通过多目标遗传算法进行进一步总结：遗传算法在多目标优化圈中为是最优的解决方法，而且它还将决策者纳入在问题讨论范围内。适合度分配方法通过遗传算法和外部决策者的相互作用以找到问题最优的解决方案，并且详细解释遗传算法和外部决策者如何通过相互作用以得出最终结果。 1.简介 求非劣解集是多目标决策的基本手段。已有成熟的非劣解生成技术本质上都是以标量优化的手段通过多次计算得到非劣解集。目前遗传算法在多目标问题中的应用方法多数是根据决策偏好信息，先将多目标问题标量化处理为单目标问题后再以遗传算法求解，仍然没有脱离传统的多目标问题分步解决的方式。在没有偏好信息条件下直接使用遗传算法推求多目标非劣解的解集的研究尚不多见。 本文根据遗传算法每代均产生大量可行解和隐含的并行性这一特点，设计了一种基于排序的表现矩阵测度可行解对所有目标总体表现好坏的向量比较方法，并通过在个体适应度定标中引入该方法，控制优解替换和保持种群多样性，采用自适应变化的方式确定交叉和变异概率，设计了多目标遗传算法(Multi Objective Genetic Algorithm, MOGA)。该算法通过一次计算就可以得到问题的非劣解集， 简化了多目标问题的优化求解步骤。 多目标问题中在没有给出决策偏好信息的前提下，难以直接衡量解的优劣，这是遗传算法应用到多目标问题中的最大困难。根据遗传算法中每一代都有大量的可行解产生这一特点，我们考虑通过可行解之间相互比较淘汰劣解的办法来达到最 后对非劣解集的逼近。 考虑一个n维的多目标规划问题，且均为目标函数最大化， 其劣解可以定义为： f i (x * )≤f i (x t ) i=1，2，??，n (1) 且式(1)至少对一个i取“＜”。即至少劣于一个可行解的x必为劣解。 对于遗传算法中产生大量的可行解，我们考虑对同一代中的个体基于目标函数相互比较，淘汰掉确定的劣解，并以生成的新解予以替换。经过数量足够大的种群一定次数的进化计算，可以得到一个接近非劣解集前沿面的解集，在一定精度要求下，可以近似的将其作为非劣解集。 个体的适应度计算方法确定后，为保证能得到非劣解集，算法设计中必须处理好以下问题：(1)保持种群的多样性及进化方向的控制。算法需要求出的是一组不同的非劣解，所以计算中要防止种群收敛到某一个解。与一般遗传算法进化到

遗传算法在多目标优化中的作用 调研报告

遗传算法在多目标优化中的作用调研报告 姓名: 学院: 班级: 学号: 完成时间:20 年月日 目录 1 .课题分析................................................................................................................................ 0 2 .检索策略................................................................................................................................ 0 2.1 检索工具的选择................................................................................................................................ ......... 0 2.2 检索词的选择................................................................................................................................ ............. 0 2.3 通用检索式................................................................................................................................ .. 0 3.检索步骤及检索结果 0 3.1 维普中文科技期刊数据库 0 3.2 中国国家知识产权局数据

多目标遗传算法代码

. % function nsga_2(pro) %% Main Function % Main program to run the NSGA-II MOEA. % Read the corresponding documentation to learn more about multiobjective % optimization using evolutionary algorithms. % initialize_variables has two arguments; First being the population size % and the second the problem number. '1' corresponds to MOP1 and '2' % corresponds to MOP2. %inp_para_definition=input_parameters_definition; %% Initialize the variables % Declare the variables and initialize their values % pop - population % gen - generations % pro - problem number %clear;clc;tic; pop = 100; % 每一代的种群数 gen = 100; % 总共的代数 pro = 2; % 问题选择1或者2，见switch switch pro case 1 % M is the number of objectives. M = 2; % V is the number of decision variables. In this case it is % difficult to visualize the decision variables space while the % objective space is just two dimensional. V = 6; case 2 M = 3; V = 12; case 3 % case 1和case 2 用来对整个算法进行常规验证，作为调试之用；case 3 为本工程所需； M = 2; %(output parameters 个数) V = 8; %(input parameters 个数) K = 10; end % Initialize the population chromosome = initialize_variables(pop,pro); %% Sort the initialized population % Sort the population using non-domination-sort. This returns two columns % for each individual which are the rank and the crowding distance

多目标规划遗传算法

%遗传算法解决多目标函数规划 clear clc syms x; %Function f1=f(x) f1=x(:,1).*x(:,1)/4+x(:,2).*x(:,2)/4; %function f2=f(x) f2=x(:,1).*(1-x(:,2))+10; NIND=100; MAXGEN=50; NV AR=2; PRECI=20; GGPA=0.9; trace1=[]; trace2=[]; trace3=[]; FielD=[rep([PRECI],[1,NV AR]);[1,1;4,2];rep([1;0;1;1],[NV AR])]; Chrom=crtbp(NIND,NV AR*PRECI); v=bs2rv(Chrom,FielD); gen=1; while gen

遗传算法多目标函数优化

多目标遗传算法优化 铣削正交试验结果 说明： 1.建立切削力和表面粗糙度模型 如： 3.190.08360.8250.5640.45410c e p z F v f a a -=（1） a R =此模型你们来拟合（上面有实验数据，剩下的两个方程已经是我帮你们拟合好的了）（2） R a =10?0.92146v c 0.14365f z 0.16065a e 0.047691a p 0.38457 10002/c z p e Q v f a a D π=-????（3） 变量约束范围：401000.020.080.25 1.0210c z e p v f a a ≤≤??≤≤??≤≤? ?≤≤? 公式（1）和（2）值越小越好，公式（3）值越大越好。π=3.14 D=8 2.请将多目标优化操作过程录像（同时考虑三个方程，优化出最优的自变量数值），方便我后续进行修改；将能保存的所有图片及源文件发给我；将最优解多组发给我，类似于下图（黄色部分为达到的要求）

遗传算法的结果:

程序如下: clear; clc; % 遗传算法直接求解多目标优化 D=8; % Function handle to the fitness function F=@(X)[10^(3.19)*(X(1).^(-0.0836)).*(X(2).^0.825).*(X(3).^0.564).*(X(4).^0. 454)]; Ra=@(X)[10^(-0.92146)*(X(1).^0.14365).*(X(2).^0.16065).*(X(3).^0.047691).*( X(4).^0.38457)]; Q=@(X)[-1000*2*X(1).*X(2).*X(3).*X(4)/(pi*D)];

遗传算法程序代码--多目标优化--函数最值问题

函数最值问题：F=X2+Y2-Z2, clear clc %%初始化 pc=0.9; %交叉概率 pm=0.05; %变异概率 popsize=500; chromlength1=21; chromlength2=23; chromlength3=20; chromlength=chromlength1+chromlength2+chromlength3; pop=initpop(popsize,chromlength);% 产生初始种群 for i=1:500 [objvalue]=calobjvalue(pop); %计算目标函数值 [fitvalue]=calfitvalue(objvalue);%计算个体适应度 [newpop]=selection(pop,fitvalue);%选择 [newpop1]=crossover(newpop,pc) ; %交叉 [newpop2]=mutation(newpop1,pm) ;%变异 [newobjvalue]=newcalobjvalue(newpop2); %计算最新代目标函数值 [newfitvalue]=newcalfitvalue(newobjvalue); % 计算新种群适应度值[bestindividual,bestfit]=best(newpop2,newfitvalue); %求出群体中适应值最大的个体及其适应值 y(i)=max(bestfit); %储存最优个体适应值 pop5=bestindividual; %储存最优个体 n(i)=i; %记录最优代位置 %解码 x1(i)=0+decodechrom(pop5,1,21)*2/(pow2(21)-1); x2(i)=decodechrom(pop5,22,23)*6/(pow2(23)-1)-1; x3(i)=decodechrom(pop5,45,20)*1/(pow2(20)-1); pop=newpop2; end %%绘图 figure(1)%最优点变化趋势图 i=1:500; plot(y(i),'-b*') xlabel('迭代次数'); ylabel('最优个体适应值'); title('最优点变化趋势'); legend('最优点');

多目标遗传算法中文【精品毕业设计】(完整版)

一种在复杂网络中发现社区的多目标遗传算法 Clara Pizzuti 摘要——本文提出了一种揭示复杂网络社区结构的多目标遗传算法。该算法优化了两个目标函数，这些函数能够识别出组内节点密集连接，而组间连接稀疏。该方法能产生一系列不同等级的网络社区，其中解的等级越高，由更多的社区组成，被包含在社区较少的解中。社区的数量是通过目标函数更佳的折衷值自动确定的。对合成和真实网络的实验，结果表明算法成功地检测到了网络结构，并且能与最先进的方法相比较。 关键词：复杂网络，多目标聚类，多目标进化算法 1、简介 复杂网络构成了表示组成许多真实世界系统的对象之间关系的有效形式。协作网络、因特网、万维网、生物网络、通信传输网络，社交网络只是一些例子。将网络建模为图，节点代表个体，边代表这些个体之间的联系。 复杂网络研究中的一个重要问题是社区结构[25]的检测，也被称作为聚类[21]，即将一个网络划分为节点组，称作社区或簇或模块，组内连接紧密，组间连接稀疏。这个问题，如[21]指出，只有在建模网络的图是稀疏的时候才有意义，即边的数量远低于可能的边数，否则就类似于数据簇[31]。图的聚类不同于数据聚类，因为图中的簇是基于边的密度，而在数据聚类中，它们是与距离或相似度量紧密相关的组点。然而，网络中社区的概念并未严格定义，因为它的定义受应用领域的影响。因此，直观的理解是同一社区内部边的数量应该远多于连接图中剩余节点的边的数量，这构成了社区定义的一般建议。这个直观定义追求两个不同的目标：最大化内部连接和最小化外部连接。 多目标优化是一种解决问题的技术，当多个相互冲突的目标被优化时，成功地找到一组解。通过利用帕累托最优理论[15]获得这些解，构成了尽可能满足所有目标的全局最优解。解决多目标优化问题的进化算法取得成功，是因为它们基于种群的特性，同时产生多个最优解和一个帕累托前沿[5]的优良近似。 因此，社区检测能够被表述为多目标优化问题，并且帕累托最优性的框架可以提供一组解对应于目标之间的最佳妥协以达到最优化。事实上，在上述两个目标之间有一个折衷，因为当整个网络社区结构的外部连接数量为空时，那它就是最小的，然而簇密度不够高。 在过去的几年里，已经提出了许多方法采用多目标技术进行数据聚类。这些方法大部分在度量空间[14], [17],[18], [28], [38], [39], [49], [51]聚集目标，虽然[8]中给出了分割图的一个方法，并且在[12]中描述了网络用户会议的一个图聚类算法。 本文中，一个多目标方法，名为用于网络的多目标遗传算法(MOGA-Net)，通过利用提出的遗传算法发现网络中的社区。该方法优化了[32]和[44]中介绍的两个目标函数，它们已被证实在检测复杂网络中模块的有效性。第一个目标函数利用了community score的概念来衡量对一个网络进行社区划分的质量。community score值越高，聚类密度越高。第二个目标函数定义了模块中节点fitness的概念，并且反复迭代找到节点fitness总和最大的模块，以下将这个目标函数称为community fitness。当总和达到最大时，外部连接是最小。两个目标函数都有一个正实数参数控制社区的规模。参数值越大，找到的社区规模越小。MOGA-Net利用这两个函数的优点，通过有选择地探索搜寻空间获得网络中存在的社区，而不需要提前知道确切的社区数目。这个数目是通过两个目标之间的最佳折衷自动确定的。 多目标方法的一个有趣结果是它提供的不是一个单独的网络划分，而是一组解。这些解中的每一个都对应两个目标之间不同的折衷，并对应多种网络划分方式，即由许多不同簇组成。对合成网络和真实网络的实验表明，这一系列帕累托最优解揭示了网络的分层结构，其中簇的数目较多的解包含在社区数目较少的解中。多目标方法的这个特性提供了一个很好的机会分析不同层级

遗传算法在多目标线性规划的应用

龙源期刊网 https://www.wendangku.net/doc/9912052873.html, 遗传算法在多目标线性规划的应用 作者：陈紫电 来源：《新课程·上旬》2013年第11期 摘要：求解多目标线性规划的基本思想大都是将多目标问题转化为单目标规划，目前主 要有线性加权和法、最大最小法、理想点法等。然而实际问题往往是复杂的，究竟哪种方法更加有效，也是因题而异。因此，通过讨论各种方法，提出了一个对各种算法的优劣进行量化对比的方法，并运用Matlab软件设计了相应的遗传算法来实现求解。 关键词：多目标线性规划；Matlab；遗传算法 多目标线性规划是最优化理论的重要组成部分，由于各目标之间的矛盾性和不可公度性，要使所有目标均达到最优，基本上是不可能的，因此，多目标规划问题往往只是求其相对较优的解。目前，求解多目标线性规划问题的有效方法有理想点法、线性加权和法、最大最小法、目标规划法，然而这些方法对多目标偏好信息的确定、处理等方面的研究工作不够深入，本文对多目标线性规划各解法的优劣进行了量化比较，最后还设计了相应的遗传算法，并借助MATLAB实现求解。 一、多目标线性规划模型 多目标线性规划有着两个和两个以上的目标函数，且目标函数和约束条件全是线性函数，其数学模型表示为： 二、多目标线性规划的求解方法 1.理想点法 三、遗传算法 对于上述多目标规划问题的各种解法，都从一定程度上有各自的偏好。为此，我们提出了一种多目标规划问题的遗传算法。 本文对各分量都做了数据标准化，并以（1，1，…，1）为理想目标，再以目标值的距离为目标（此距离可以作为其他算法的评价），消除了各分量之间的不公平性，最后借助MATLAB软件，从结果上看最后得到了更为合理的目标值。 参考文献： [1]李荣钧.多目标线性规划模糊算法与折衷算法分析[J].运筹与管理，2001，10（3）：13-18.

多目标遗传算法代码

% function nsga_2(pro) %% Main Function % Main program to run the NSGA-II MOEA. % Read the corresponding documentation to learn more about multiobjective % optimization using evolutionary algorithms. % initialize_variables has two arguments; First being the population size % and the second the problem number. '1' corresponds to MOP1 and '2' % corresponds to MOP2. %inp_para_definition=input_parameters_definition; %% Initialize the variables % Declare the variables and initialize their values % pop - population % gen - generations % pro - problem number %clear;clc;tic; pop = 100; % 每一代的种群数 gen = 100; % 总共的代数 pro = 2; % 问题选择1或者2，见switch switch pro case 1 % M is the number of objectives. M = 2; % V is the number of decision variables. In this case it is % difficult to visualize the decision variables space while the % objective space is just two dimensional. V = 6; case 2 M = 3; V = 12; case 3 % case 1和case 2 用来对整个算法进行常规验证，作为调试之用；case 3 为本工程所需； M = 2; %(output parameters 个数) V = 8; %(input parameters 个数) K = 10; end % Initialize the population chromosome = initialize_variables(pop,pro); %% Sort the initialized population % Sort the population using non-domination-sort. This returns two columns % for each individual which are the rank and the crowding distance % corresponding to their position in the front they belong. 真是牛X了。 chromosome = non_domination_sort_mod(chromosome,pro); %% Start the evolution process

多目标优化实例和matlab程序

NSGA-II 算法实例 目前的多目标优化算法有很多, Kalyanmoy Deb 的带精英策略的快速非支配排序遗传算法(NSGA-II) 无疑是其中应用最为广泛也是最为成功的一种。本文用的算法是MATLAB 自带的函数gamultiobj ，该函数是基于NSGA-II 改进的一种多目标优化算法。 一、 数值例子 多目标优化问题 424221********* 4224212212112 12min (,)10min (,)55..55 f x x x x x x x x x f x x x x x x x x x s t x =-++-=-++-≤≤??-≤≤? 二、 Matlab 文件 1． 适应值函数m 文件： function y=f(x) y(1)=x(1)^4-10*x(1)^2+x(1)*x(2)+x(2)^4-x(1)^2*x(2)^2; y(2)=x(2)^4-x(1)^2*x(2)^2+x(1)^4+x(1)*x(2); 2． 调用gamultiobj 函数，及参数设置： clear clc fitnessfcn=@f; %适应度函数句柄 nvars=2; %变量个数 lb=[-5,-5]; %下限 ub=[5,5]; %上限 A=[];b=[]; %线性不等式约束 Aeq=[];beq=[]; %线性等式约束 options=gaoptimset('paretoFraction',0.3,'populationsize',100,'generations', 200,'stallGenLimit',200,'TolFun',1e-100,'PlotFcns',@gaplotpareto); % 最优个体系数paretoFraction 为0.3；种群大小populationsize 为100，最大进化代数generations 为200， % 停止代数stallGenLimit 为200， 适应度函数偏差TolFun 设为1e-100，函数gaplotpareto ：绘制Pareto 前端 [x,fval]=gamultiobj(fitnessfcn,nvars,A,b,Aeq,beq,lb,ub,options)

多变量多目标的遗传算法程序

这是我在解决电梯动力学参数写的简单遗传算法（程序带目标函数值、适应度值计算，但是我的适应度函数因为目标函数的计算很特殊，一起放在了程序外面计算,在此不提供）。 头文件： // CMVSOGA.h : main header file for the CMVSOGA.cpp // 本来想使用链表里面套链表的，程序调试比较麻烦，改为种群用链表表示 //染色体固定为16的方法。 #if !defined(AFX_CMVSOGA_H__45BECA_61EB_4A0E_9746_9A94D1CCF767_ _INCLUDED_) #define AFX_CMVSOGA_H__45BECA_61EB_4A0E_9746_9A94D1CCF767__INCLUDED _ #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 #include "Afxtempl.h" #define variablenum 16 class CMVSOGA { public: CMVSOGA(); void selectionoperator(); void crossoveroperator(); void mutationoperator(); void initialpopulation(int, int ,double ,double,double *,double *); //种群初始化 void generatenextpopulation(); //生成下一代种群 void evaluatepopulation(); //评价个体，求最佳个体 void calculateobjectvalue(); //计算目标函数值 void calculatefitnessvalue(); //计算适应度函数值 void findbestandworstindividual(); //寻找最佳个体和最差个体 void performevolution(); void GetResult(double *); void GetPopData(double **); void SetValueData(double *); void maxandexpectation(); private: struct individual { double chromosome[variablenum]; //染色体编码长度应该为变量的个数 double value; double fitness; //适应度 };

MATLAB课程遗传算法实验报告及源代码

硕士生考查课程考试试卷 考试科目：MATLAB教程 考生姓名：张宜龙考生学号：2130120033 学院：管理学院专业：管理科学与工程考生成绩： 任课老师(签名) 考试日期：年月日午时至时

《MATLAB 教程》试题： A 、利用MATLA B 设计遗传算法程序，寻找下图11个端点的最短路径，其中没有连接的端点表示没有路径。要求设计遗传算法对该问题求解。 a e h k B 、设计遗传算法求解f (x)极小值，具体表达式如下： 3 21231(,,)5.12 5.12,1,2,3 i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 C 、利用MATLAB 编程实现：三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的大权掌握在商人手中，商人们怎样才能安全渡河？ D 、结合自己的研究方向选择合适的问题，利用MATLAB 进行实验。 以上四题任选一题进行实验，并写出实验报告。

选择题目： B 、设计遗传算法求解f (x)极小值，具体表达式如下： 3 21231(,,)5.12 5.12,1,2,3 i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 一、问题分析（10分） 这是一个简单的三元函数求最小值的函数优化问题，可以利用遗传算法来指导性搜索最小值。实验要求必须以matlab 为工具，利用遗传算法对问题进行求解。 在本实验中，要求我们用M 函数自行设计遗传算法，通过遗传算法基本原理，选择、交叉、变异等操作进行指导性邻域搜索，得到最优解。 二、实验原理与数学模型（20分） （1）试验原理： 用遗传算法求解函数优化问题，遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。其采纳了自然进化模型，从代表问题可能潜在解集的一个种群开始，种群由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体；初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：在每一代，概据问题域中个体的适应度大小挑选个体；并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。这一过程循环执行，直到满足优化准则为止。最后，末代个体经解码，生成近似最优解。基于种群进化机制的遗传算法如同自然界进化一样，后生代种群比前生代更加适应于环境，通过逐代进化，逼近最优解。 遗传算法是一种现代智能算法，实际上它的功能十分强大，能够用于求解一些难以用常规数学手段进行求解的问题，尤其适用于求解多目标、多约束，且目标函数形式非常复杂的优化问题。但是遗传算法也有一些缺点，最为关键的一点，即没有任何理论能够证明遗传算法一定能够找到最优解，算法主要是根据概率论的思想来寻找最优解。因此，遗传算法所得到的解只是一个近似解，而不一定是最优解。 （2）数学模型 对于求解该问题遗传算法的构造过程： （1）确定决策变量和约束条件；

非线性整数规划的遗传算法Matlab程序

非线性整数规划的遗传算法Matlab程序（附图） 通常，非线性整数规划是一个具有指数复杂度的NP问题，如果约束较为复杂，Matlab优化工具箱和一些优化软件比如lingo等，常常无法应用，即使能应用也不能给出一个较为令人满意的解。这时就需要针对问题设计专门的优化算法。下面举一个遗传算法应用于非线性整数规划的编程实例，供大家参考！ 模型的形式和适应度函数定义如下： 这是一个具有200个01决策变量的多目标非线性整数规划，编写优化的目标函数如下，其中将多目标转化为单目标采用简单的加权处理。 function Fitness=FITNESS(x,FARM,e,q,w) %% 适应度函数 % 输入参数列表 % x 决策变量构成的4×50的0-1矩阵 % FARM 细胞结构存储的当前种群，它包含了个体x % e 4×50的系数矩阵 % q 4×50的系数矩阵 % w 1×50的系数矩阵 %%

gamma=0.98; N=length(FARM);%种群规模 F1=zeros(1,N); F2=zeros(1,N); for i=1:N xx=FARM{i}; ppp=(1-xx)+(1-q).*xx; F1(i)=sum(w.*prod(ppp)); F2(i)=sum(sum(e.*xx)); end ppp=(1-x)+(1-q).*x; f1=sum(w.*prod(ppp)); f2=sum(sum(e.*x)); Fitness=gamma*sum(min([sign(f1-F1);zeros(1,N)]))+(1-gamma )*sum(min([sign(f2-F2);zeros(1,N)])); 针对问题设计的遗传算法如下，其中对模型约束的处理是重点考虑的地方function [Xp,LC1,LC2,LC3,LC4]=MYGA(M,N,Pm) %% 求解01整数规划的遗传算法 %% 输入参数列表 % M 遗传进化迭代次数 % N 种群规模 % Pm 变异概率 %% 输出参数列表 % Xp 最优个体 % LC1 子目标1的收敛曲线 % LC2 子目标2的收敛曲线 % LC3 平均适应度函数的收敛曲线 % LC4 最优适应度函数的收敛曲线 %% 参考调用格式[Xp,LC1,LC2,LC3,LC4]=MYGA(50,40,0.3)

非线性整数规划的遗传算法Matlab程序

非线性整数规划的遗传算法Matlab程序 通常，非线性整数规划是一个具有指数复杂度的NP问题，如果约束较为复杂，Matlab优化工具箱和一些优化软件比如lingo等，常常无法应用，即使能应用也不能给出一个较为令人满意的解。这时就需要针对问题设计专门的优化算法。下面举一个遗传算法应用于非线性整数规划的编程实例，供大家参考！ 模型的形式和适应度函数定义如下： 这是一个具有200个01决策变量的多目标非线性整数规划，编写优化的目标函数如下，其中将多目标转化为单目标采用简单的加权处理。 function Fitness=FITNESS(x,FARM,e,q,w) %% 适应度函数 % 输入参数列表 % x 决策变量构成的4×50的0-1矩阵 % FARM 细胞结构存储的当前种群，它包含了个体x % e 4×50的系数矩阵 % q 4×50的系数矩阵

% w 1×50的系数矩阵 %% gamma=0.98; N=length(FARM);%种群规模 F1=zeros(1,N); F2=zeros(1,N); for i=1:N xx=FARM{i}; ppp=(1-xx)+(1-q).*xx; F1(i)=sum(w.*prod(ppp)); F2(i)=sum(sum(e.*xx)); end ppp=(1-x)+(1-q).*x; f1=sum(w.*prod(ppp)); f2=sum(sum(e.*x)); Fitness=gamma*sum(min([sign(f1-F1);zeros(1,N)]))+(1-gamma)*sum(min([sign(f2-F2);zeros(1,N)])); 针对问题设计的遗传算法如下，其中对模型约束的处理是重点考虑的地方 function [Xp,LC1,LC2,LC3,LC4]=MYGA(M,N,Pm) %% 求解01整数规划的遗传算法 %% 输入参数列表 % M 遗传进化迭代次数 % N 种群规模 % Pm 变异概率 %% 输出参数列表 % Xp 最优个体 % LC1 子目标1的收敛曲线 % LC2 子目标2的收敛曲线 % LC3 平均适应度函数的收敛曲线 % LC4 最优适应度函数的收敛曲线 %% 参考调用格式[Xp,LC1,LC2,LC3,LC4]=MYGA(50,40,0.3) %% 第一步：载入数据和变量初始化 load eqw;%载入三个系数矩阵e,q,w %输出变量初始化 Xp=zeros(4,50); LC1=zeros(1,M); LC2=zeros(1,M); LC3=zeros(1,M); LC4=zeros(1,M); Best=inf; %% 第二步：随机产生初始种群