第２５卷第２期 ２ ０ １ ２年５月 青岛大学学报（自然科学版） ＪＯＵＲＮＡＬ ＯＦ ＱＩＮＧＤＡＯ ＵＮＩＶＥＲＳＩＴＹ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ） Ｖｏ１．２５ ＮＯ．２ Ｍａｖ ２ ０ １ ２ 文章编号：１００６—１０３７（２０１２）０２—００２１—０４ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００６—１０３７．２０１２．０５．００４ 一个关于Ｌｉｐｓｃｈｉｔｚ函数的全局优化算法 杨婷婷，田志远 ，黎 博，汪雪萍 （青岛大学数学科学学院，山东青岛２６６０７１） 摘要：研究了关于Ｌｉｐｓｃｈｉｔｚ函数的全局优化算法，把辐射状细分的剖分技术和二分法运 用到单纯形算法中，充分利用当前计算所得到的最优信息，结合分支定界单纯形的优势， 改进了单纯形算法，分析了算法的可行性，并给出了算法的收敛性证明。 关键词：全局优化；Ｌｉｐｓｃｈｉｔｚ函数；单纯形 中图分类号：０２２１．２ 主题分类号：９０Ｃ２５ 文献标志码：Ａ １ 问题 Ｌｉｐｓｃｈｉｔｚ优化问题是全局优化的一种特殊形式，考虑下面问题 ｍｉｎｆ（－ｚ） ３－∈尸 （１） 求ｚ ，使得ｆ（ｘ ）≤厂（ｚ），Ｖ－ｚ∈Ｐ，其中Ｐ是在．Ｒ”上具有非空内点的多胞形，即Ｐ一｛ｚ∈Ｒ”ｌ Ａｘ≤ ｂ｝，Ａ＝（ｎ ，ａ “，ａ ） Ｅ Ｒ ，ｂ∈Ｒ 。ｆ是定义在Ｓ上的Ｌｉｐｓｃｈｉｔｚ函数，即厂满足 １＿厂（ｚ）～厂（ ）Ｉ≤Ｌ Ｉ ｌｚ—Ｙ＿ｌ，Ｖ－ｚ， ∈Ｓ 为单纯形的顶点。我们把这种问题称为Ｌｉｐｓｃｈｉｔｚ优化问题。 （２） 其中Ｉｌ・ｌｌ表示Ｅｕｃｌｉｄｅａｎ范数，且ＰＣＳ，Ｓ为单纯形，即Ｓ可以表示Ｓ—Ｉ－ｖ０， ，…， ］，其中 ｏ，７２ ，…， ２ 最优下界 根据厂的解析性质，Ｐ为单纯形，且有 厂（ ）一Ｌ ｌｌ 一 ｌｌ≤厂（ｚ）≤＿厂（ｙ）＋Ｌ ｌＩ ｚ一 ｌｌ，Ｖｚ，Ｙ∈Ｓ 若 ∈Ｐ固定，则 Ｆｙ（ｘ）一＿厂（ ）一Ｌ ｌ ｌｚ— ｌ ｌ是，（ｚ）在Ｐ上的下界估计。下面我们引进凸包络的定义，它在全局优化算法的研究中占有重要作用。 （４） （３） 命题２．１设厂：ｓ一尺是下半连续函数，其中ｓ是Ｒ 中非空凸集，则称 （．ｚ）是－厂（ｚ）在５上的凸包络，如果 （－ｚ）满足： （１） （ｚ）在Ｓ上是凸的； （２） （ｚ）≤，（ｚ），对所有的 ∈Ｓ； （３）若ｈ（ｚ）是任意一个定义在Ｓ上的凸函数，并且对于所有ｚＥＳ，ｈ（ｚ）≤厂（ｚ），则有ｈ（ ）≤ （ｚ）。 根据这个定义，函数的凸包络实际上是该函数在ｓ上的最佳一致凸下方估计。 引理２．１对于ｍｉｎｆ（ｘ），其中ｓ是尺”中紧凸集。令 （ｚ）是函数厂（ ）在Ｓ上的凸包络，则有 ｆ 一ｍｉｎ｛－厂（ｚ）ｌ ∈Ｓ｝一ｒａｉｎ｛ （ｚ）ｌ ｚＥ Ｓ）且 ２Ｏ１ ｌ—ｌ２一ｌ２ ＊收稿日期： 基金项目： 山东省高等学校科技计划项目（ＪＩＯＬＡ０５） 作者简介： 杨婷婷（１９８６一），女，山东人，硕士研究生，研究方向为计算数学。 ＊通讯作者： 田志远，青岛大学数学科学学院教授。Ｅ—ｍａｉｌ：ｔｔｔｓｓｘ＠１２６．ｃｏｒｎ ２２ 青岛大学学报（自然科学版） ｛Ｙ∈Ｓ１ （ ）一ｆ ｝ ｛Ｙ∈Ｓ｝ （ ）一－厂 ）。 第２５卷 此引理表明，为了求解最优问题，我们可以求解其相应的凸包络的优化问题。 定理２・１口 设Ｓ—Ｉｖ。，Ｖ ，…，Ｖ ］是，卜单纯形。令ｆ：Ｓ－－－￣Ｒ是Ｓ上的凹函数则ｆ在Ｓ上的凸包络 是 。仿射函数，且满足 （ ）一ｆ（ｖ ），０≤ ≤ ， 若ｚ∈ｓ∞ｚ一∑ ，∑ ＝＝＝１， ≥０，０≤ｉ≤竹， ０ ０ （ｚ）一∑Ａ ｆ（ｖ ） ０ 这里我们可以看到，由 于ｚ的相关性，我们也可记成 （ｚ）一∑Ａ￣ｆ（ｖ ）。 命题２．２设ｓ是单纯形，Ｐ是Ｒ 上的多胞形。令Ｑ是Ｓ的有限点集，，是定义在Ｓ上的利普希兹函数，且 已知Ｌｉｐｓｃｈｉｔｚ常数Ｌ。对于每个ｙＥＱ，令 表示凹函数Ｆ （ ）一，（ ）一Ｌ ｌ ｌｘ－－ｙ ｌｌ在ｓ上的凸包络。则 线性规划 ａｒｉｎ ｔ Ｓ．ｔ． （Ｌｚ）≤ ，ｙＥＱ ｚ∈ＳｎＰ （５） 的最优值 （５ ｎ Ｐ）是ｍｉｎ｛ｆ（ｘ）ｅ ｚ∈Ｓｎ Ｐ｝的下界，且当Ｓ ｎ Ｐ一 时 （Ｓ ｎ Ｐ）一。。。我们记 （Ｓ ｎ Ｐ）一 （Ｓ），当前最优点ｚ 一ｃｏ（Ｓ）。 （Ｓ）为Ｓ的可行顶点集。 ３单纯形算法 下面给出用来求解问题（１）的单纯形算法，下界 （ｓ）由命题２．２给出。 算法３．１ Ｓｔｅｐ ０ 初始 单纯形Ｓ。 Ｐ，０＜￡＜１， 。一 （ｓ。），７０一ｒａｉｎ｛厂（ｚ）ｆ ３７．∈Ｑ。｝，Ｑ。一Ｔｏ Ｕ （Ｓ。），其中Ｔ。 是Ｓ。在某种概率分布下产生的样本点集， 一｛Ｓ。）， 。＝＝：｛Ｙ∈Ｑ。ｌ，（ ）一ｙｏ），ｋ一０。 Ｓｔｅｐ １ 若 一 ≤￡或Ｍ 一 ，则算法停止， 为近似最优值， 一｛ ∈ ｌ厂（ ）＝ ）为最优点集；否 则，选取Ｓ ∈Ｍ，使得 （Ｓ ）一ｐ－ ，及相应的最优点 （Ｓ ），令ｙ＝：： 。 Ｓｔｅｐ ２依点叫（ｓ ）对ｓ 进行辐射状细分。 （Ｓ ）：：＝ ＋…＋ ＋…＋ ，将ｓ 剖分成Ｐ个（正 的 的个数）单纯形，其中Ｓ 一［ ，…， ，∞（ｓ）， ”， ］∈Ｉ１，当且仅当 ＞Ｏ。对于工１中的每个单纯 形，求解问题（２）得 （５ ），及相应的 （ｓ ），ｉ—ｌ，…，Ｐ，同时更新ｙ的值。检查 中的每个单纯形是否满足 ｙ－－／ｚ（Ｓ ）＜（１－－ｓ）（ 一 ）。 Ｓｔｅｐ ３ 对于ｒ中不满足条件的单纯形ｓ ，以ｓ 最长的边的中点为基准将其对分，直至满足ｙ一 （Ｓ ） ＜（１－－ｓ）（ －－Ｆ ），同时更新），的值。 Ｓｔｅｐ ４ 令Ｑ ＋ｌ—Ｑ Ｕ （Ｓ ＋１）， ＋】一ｒａｉｎ｛ｙ，－厂（∞（Ｓ ））｝，ｉ一１，…，Ｐ。 Ｍｋ＋ 一（ ＵＩ１）＼｛Ｓ ）， ＋ 一 ＼｛Ｓ ｌ（Ｓ）≥ｙ ），／／￣＋ｉ—ｒａｉｎ｛ （Ｓ）ｌ Ｓ∈ ），令ｋ：一ｋ＋１，返回第１ 步。 ４收敛性分析 定义４．Ｉ 令ｓ是 一单纯形，顶点集为 （ｓ）一（ 。，７３ 一，７３ ｝。选择一个点叫∈Ｓ且 （ｓ），它可以惟一的 表示成 ：∑ ， ≥０，（ 一０，１，…， ），∑ 一１。对于每个使Ａｉ＞０的 ，用叫代替顶点 ，构建单纯 ０ ０ 形Ｓ（ｉ， ），即 Ｓ（ｉ，叫）＝＝＝ＣＯ｛ ｏ，…， 一１， ， 汁１，…，７３ ｝。 这种细分称为辐射状细分，也称 细分。 第２期 杨婷婷，等：一个关于Ｌｉｐｓｃｈｉｔｚ函数的全局优化算法 ２３ 若∞取Ｓ最长边的中点，则Ｓ被分成两个子单纯形，我们把这种细分称为对分或二分。 命题４．２对于以单纯形Ｓ最长的边的中点为基准的对分法，在对分下，Ｓ 的直径ａ（Ｓ ）逐渐减小，则当忌一 。。时， （Ｓ ）一０。 根据辐射状细分的定义，设ｓ ＋ 是由Ｓ 生成的一个子单纯形，对于 ∈Ｓｋ＋ ，ｚ— ｏ ＋…＋ ＋…＋ ，其中Ａｉ≥０，∑ 一１，有 ｓ （Ｉｚ）≥ ｓ （ ）。 初 定理４．１ （１）算法３．１在￡＞Ｏ时，有限步迭代停止。 （２）若算法３．１无限进行，则由算法生成的无限序列｛ｙｋ），有 １ｉｍ ＾一ｌｉｍｆ（ｙ ）一ｌｉｍｙｋ 始 ０ 且由序列｛ ）产生的每个聚点Ｙ 是问题ｍｉｎｆ （ｚ）的最优点。 一 一 证明 设 是序列｛ ｝ＣＰ产生的一个聚点，令厂 ＝ｍｉｎ｛ｆ（ｘ）ｌ ｚ∈Ｐ）。序列｛ ｝是－厂 单调上升的下界。 ８ Ｏ 序列｛ｙ ｝是厂 单调下降的上界，且有 一 ｉｍ 的存在。由 （ｚ）的连续性，可知 ＝ｆ（Ｙｋ），由于 一 ≥ ７ ｌ ０，则ｌｉａ（ｒ 一 ）一０。ｙ 一ｌｉｍ７女 ｋ— ∞ —÷ｏ。 ／Ｌ Ｓ ０ 我们用反证法。假设存在一个￡。＞０，使得 ｉｍ（ －－，ｕｋ）：ｅ。，由此，我们得不妨取一个ｏ＜艿＜ ，，． 一、，，存在 １ ．．．．．．．．．．．．．．．．，．．．．． ．．．．．一 个Ｋ＞０，当忌＞Ｋ时，有 一 ＜￡。＋ 。则 ｙ女＋ｌ－－￣ｚ ＋ｌ＜（１一￡）（ －－／ｚ ）＜（１－－ｓ）（￡０＋ ）≤（１一￡）（Ｓｏ＋ ）一ｅｏ １ ２ Ｏ Ｏ ８ ●●●●●●●●●●●●ｆ●●‘●●●●Ｊ由此，假设不成立。 又由 Ｏ 一 ≤ｆ ≤）， 一ｆ（Ｙ ）一ｌｉｍｆ（ｙ ）， 从而 ｌｉｍ ＾一ｌｉｍｆ（ｙ＾）一ｌｉｍ７ ， ｌｉｍ 一ｌｉｍｆ（ｙ＾）一ｌｉｍ７ ，且ｆ（Ｙ ）一厂 。即证结论。 ∞ —＋∞ —’。。 １ 口 对于ｍｉｎ—ｌ ｚ ＋寺３２ ＋÷ｚ。Ｉ专一３２；，Ｐ一｛３２∈Ｒ。Ｉ Ａｘ≤ｂ，３２≥０｝为多胞形，其中Ａ一 １ １ １ １ —１ —１／４ ．２ —２ Ｏ Ｏ １ １ ｂ一 由 ＜ ，对Ｓ。辐射状剖分，得 （Ｓ…）：一３．７２２， （Ｓｌｌ２）一一３．７２２， （ｓ ，ｓ）一～６，ｙ 一一３．７２２，由于 （ｓ１．１）一 （Ｓ１，２）一），１知最优值－厂 一 ３．７２２。由于 （Ｓ１Ｉ３）＜ ，对ｓ 进行辐射状剖分， （Ｓｚ， ）一一３．７２２， （Ｓｚ。ｚ）一一３．７２２，），ｚ一一３．７２２。 此时 ｚ—ｙｚ，算法结束。最优值为一３．７２２，最优解为（１．２，０，０．８） 。 通过此例子，可以知道，算法３．１可以解决此类优化问题且比单一的二分法［１］更简洁。 ５ 总 结 辐射状细分是单纯形算法中的一种重要剖分技术，虽然其收敛性在很长一段时间内都未得到证明，但 Ｈｏｒｓｔ￣Ｔｈｏａｉ给出许多数值试验，表明这种剖分比纯粹的对分能产生较好的数值结果［１］。本文充分利用 了优化问题的特殊结构，把辐射状细分技术和二分法结合起来，提高了算法的可行性，并证明了算法的收敛 性。 参考文献： ［１］Ｈｏｒｓｔ Ｒ，Ｐａｒｄａｌｏｓ Ｐ Ｍ，Ｔｈｏａｉ Ｎ Ｖ，Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔＯ Ｇｌｏｂａｌ Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｍ］．Ｋｌｕｗｅｒ，Ｄｏｒｄｒｅｃｈｔ，１９９５ ［２］申培萍．全局优化方法Ｉ－Ｍ］．北京：科学出版社，２００６，７—５７． ２４ 青岛大学学报（自然科学版） 第２５卷 ｌｉ Ｍ，Ｒａｂｅｒ Ｕ，Ｏｎ Ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ｔｈｅ Ｓｉｍｐｌｉｃｉａｌ Ｂｒａｎｃｈ—ａｎｄ—Ｂｏｕｎｄ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ∞一Ｓｕｂｄｉｖｉ—ｓｉｏｎｓ ［３］ Ｌｏｃａｔｅｌ［Ｊ］． Ｊ Ｏｐｔｉｍ Ｔｈｅｏｒｙ Ａｐｐｌ，２０００，１０７：６９—７９． ［４］ Ｐｉｙａｖｓｋｉｉ，Ｓ．Ａ，Ａｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｆｉｎｄｉｎｇ ｔｈｅ ａｂｓｏｌｕｔｅ ｍｉｎｉｍｕｍ．Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｃｙｂｅｒｎｅｔｉｃｓ（ＩＫ ＡＮ ＵＳＳＲ）［Ｊ］． Ｋｉｅｖ， １９６７，１３—２４． ［５］Ｇｉａｍｐａｏｌｏ Ｌｉｕｚｚｉ，Ｓｔｅｆａｎｏ Ｌｕｅｉｄｉ，Ｖｅｒｏｎｉｃａ Ｐｉｅｃｉａｌｌｉ。Ａ ｐａｒｔｉｔｉｏｎ—ｂａｓｅｄ ｇｌｏｂａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ［Ｊ］．Ｏｌｏｂ Ｏｐｔｉｍ， ２Ｏ１Ｏ，４８：１１３—１２８． ｓｅｃｔｉｏｎ ｂｙ Ｇｌｏｂａｌ Ｏｐｔｉｍｉｚａｔｉｏｎ ［６］ Ｈｏｒｓｔ Ｒ，ＢｉＲｅｖｉｓｉｔｅｄ．［Ｊ］Ｊ．Ｏｐｔｉｍ Ｔｈｅｏｒｙ Ａｐｐ１． ２００８，１３７：１７１—１９４．ａｎｏ Ｍ，Ｌｅｒａ Ｄ，Ａ ｇｌｏｂａｌ ｍｉｎｉｍｉｚａｔｉｏｎ ［７］ Ｇａｖｉｏｐｔｉｍｉｚａｔｉｏｎ Ｌｅｔｔｅｒｓ，２００８，２：１一ｌ３ ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｌｉｐｓｃｈｉｔｚ ｆｕｎｃｔｉｏｎｓ［Ｊ］． Ａ Ｇｌｏｂａｌ Ｏｐｔｉｍｉｚａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ｏｆ Ｌｉｐｓｃｈｉｔｚ Ｆｕｎｃｔｉｏｎ ＹＡＮＧ Ｔｉｎｇ—ｔｉｎｇ，ＴＩＡＮ Ｚｈｉ—ｙｕａｎ，ＬＩ—Ｂｏ，ＷＡＮＧ Ｘｕｅ—ｐｉｎｇ （Ｃｏｌｌｅｇｅ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ，Ｑｉｎｇｄａｏ Ｕｎｉｖｅｒｓｉｔｙ，Ｑｉｎｇｄａｏ ２６６０７１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｇｌｏｂａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ｏｆ ａ Ｌｉｐｓｃｈｉｔｚ ｆｕｎｃｔｉｏｎ ｏｖｅｒ ａ ｐｏｌｙｔｏｐｅ ｉｓ ｓｔｕｄｉｅｄ．Ｉｎ ｔｈｉｓ ａｒｔｉ— ｃｌｅ。ａ ｃＵ—ｓｕｂｄｉｖｉｓｉｏｎ ａｎｄ ａ ｂｉｓｅｃｔｉｏｎ ｓｕｂｄｉｖｉｓｉｏｎ ａｒｅ ｅｍｐｌｏｙｅｄ ｉｎ ｔｈｅ ｓｉｍｐｌｅｘ ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｌｉｐｓｃｈｉｔｚ ｆｕｎｃ— ｔｉｏｎ．Ｔｈｅ ｓｉｍｐｌｅｘ ａｌｇｏｒｉｔｈｍ ｉｓ ｉｍｐｒｏｖｅｄ ｂｙ ｍａｋｉｎｇ ｆｕｌｌ ｕｓｅ ｏｆ ｔｈｅ ｂｅｓｔ ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ ａｄｖａｎｔａｇｅ ｏｆ ｔｈｅ ｂｒａｎｃｈ ｏｆ ｔｈｅ ｓｉｍｐｌｅｘ．Ｔｈｅ ｃｏｎｖｅｒｇｅｎｔ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｉｓ ｓｕｂｄｉｖｉｓｉｏｎ ｉｓ ａｌｓｏ ｐｒｏｖｅｄ． Ｋｅｙ ｗｏｒｄｓ：Ｇｌｏｂａｌ Ｏｐｔｉｍｉｚａｔｉｏｎ；Ｌｉｐｓｃｈｉｔｚ Ｆｕｎｃｔｉｏｎ；ｓｉｍｐｌｅｘ 责任编辑：乔春秀 英文编辑：张辉群 （上接第２Ｏ页） Ｄｙｎａｍｉｃ Ｎｅｔｗｏｒｋ Ｄｅｓｉｇｎ ａｎｄ Ｄｅｆｅｎｓｅ Ｐｒｉｎｃｉｐｌｅｓ ｆｏｒ ｔｈｅ Ｇｌｏｂａｌ Ｏｐｔｉｍａｌ Ｄｅｓｉｇｎｅｒ —ｒｏｎｇ， ＹＩＮ Ｌｉａｎ—ｌｉｎｇ，ＸＵＡＮ Ｈａｉ ＸＵ Ｍｉ ＧＡＯ Ｈｏｎｇ—ｗｅｉ，ＷＡＮＧ Ｇｕｉ，Ｑｉｎｇｄａｏ ２６６０７１，Ｃｈｉｎａ） （Ｃｏｌｌｅｇｅ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ，Ｑｉｎｇｄａｏ Ｕｎｉｖｅｒｓｉｔｙ， Ａｂｓｔｒａｃｔ：Ｉｎ ｔｈｉｓ ｐａｐｅｒ，Ｗｅ ｂｅｇｉｎ ｗｉｔｈ ｔｈｅ ｎｅｔｗｏｒｋ ｄｅｓｉｇｎ，ａｎｄ ａｓｓｕｍｅ ｔｈａｔ ｔｈｅ ｄｅｓｉｇｎｅｒ ａｌｓｏ ｕｎｄｅｒｔａｋｅｓ ｔｈｅ ｏｂｌｉｇａｔｉｏｎ ｏｆ ｄｅｆｅｎｄｉｎｇ ｔｈｅ ｎｅｔｗｏｒｋ ｄｕｒｉｎｇ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｄｅｓｉｇｎｉｎｇ．Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｄｉｆｆｅｒｅｎｔ ｏｒｄｅｒｓ ｏｆ ｔｈｅ ｎｅｔｗｏｒｋ ｄｅｓｉｇｎ，ｄｅｆｅｎｓｅ ａｎｄ ａｔｔａｃｋ，ｗｅ ｍａｉｎｌｙ ｄｉｓｃｕｓｓ ｔｈｅ ｄｙｎａｍｉｃ ｎｅｔｗｏｒｋ ｄｅｓｉｇｎ ｐｒｏｃｅｓｓｅｓ， ｗｈｉｃｈ ａｒｅ ｃａｒｒｉｅｄ ｏｕｔ ｂｙ ｔｈｅ ｄｅｓｉｇｎｅｒ ｏｎ ｔｈｅ ｂａｓｉｓ ｏｆ ｔｈｅ ｄｅｆｅｎｓｅ—ａｔｔａｃｋ ｒｅｓｕｌｔｓ ｏｆ ｅａｃｈ ｐｅｒｉｏｄ．Ｗｅ ｅｓｔａｂｌｉｓｈ ｔｈｅ ｇｌｏｂａｌ ｏｐｔｉｍａｌ ｐｒｉｎｃｉｐｌｅｓ ｆｏｒ ｔｈｅ ｄｅｓｉｇｎｅｒ，ｔｈａｔ ｉｓ，ｉｎ ａ ｍｕｌｔｉｐｅｒｉｏｄ ｄｙｎａｍｉｃ ｎｅｔｗｏｒｋ ｄｅｓｉｇｎ ｅｎｖｉｒｏｎ～ ｍｅｎｔ。ｔｈｅ ｐｒｉｎｃｉｐｌｅｓ ｏｆ ｔｈｅ ｄｅｓｉｇｎｅｒ ｔｏ ｍａｘｉｍｉｚｅ ｔｈｅ ｐａｙｏｆｆ ｓｕｍｍａｔｉｏｎ ｗｈｅｎ ｆａｃｉｎｇ ｔｈｅ ｓｔｒａｔｅｇｉｃ ｏｒ ｒａｎｄｏｍ ａｔｔａｃｋ． Ｂｅｓｉｄｅｓ，ｗｅ ａｌｓｏ ａｓｓｕｍｅ ｔｈａｔ ｔｈｅ ａｔｔａｃｋｅｒ ａｉｍｓ ａｔ ｍａｘｉｍｉｚｉｎｇ ｔｈｅ ｐｅｒｉｏｄ ｐａｙｏｆｆ． Ｏｕｒ ｐｒｉｍａｒｙ ｃｏｎ— ｔｒｉｂｕｔｉｏｎ ｉｓ ｇｉｖｉｎｇ ｔｈｅ ｆｕｎｄａｍｅｎｔａｌ ｐｒｉｎｃｉｐｌｅｓ ｏｆ ｔｈｅ ｄｙｎａｍｉｃ ｎｅｔｗｏｒｋ ｄｅｓｉｇｎ ａｎｄ ｄｅｆｅｎｓｅ． Ｋｅｙ ｗｏｒｄｓ：ｄｙｎａｍｉｃ ｎｅｔｗｏｒｋ ｄｅｓｉｇｎ；ｄｅｆｅｎｓｅ；ａｔｔａｃｋ；ＤＤＡ ｇａｍｅ；ＤＡＤ ｇａｍｅ 责任编辑：乔春秀 英文编辑：张辉群