基于NSGA-Ⅱ算法的多目标快速选星方法--《天文研究与技术》2018年03期
基于NSGA-Ⅱ算法的多目标快速选星方法
【摘要】：全球卫星导航系统多系统选星问题能够转化为有约束条件的多目标优化问题求解,可以同时优化几何精度因子和选星数目这两个目标,从而在减少接收机运算量的同时获得良好的定位精度。提出了一种基于NSGA-Ⅱ算法的多目标快速选星方法,该方法利用选星问题的序贯性生成初始种群,改进了约束处理方法,并选取合适的遗传算子和效用函数做出选星决策。通过仿真,证实该选星方法具有良好的可靠性和实时性,且不依赖于卫星的几何位置分布,可适用于有障碍或者遮挡的复杂情况。
【作者单位】：
【基金】：
【分类号】：P228.4
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【相似文献】
中国期刊全文数据库
徐小钧;马利华;艾国祥;;[J];天文研究与技术;2018年03期
徐小钧;马利华;艾国祥;;[J];上海交通大学学报;2017年12期
袁社旺;卓宁;;[J];中国惯性技术学报;2008年04期
倪学义，乐美龙;[J];上海海运学院学报;1996年02期
于军;邓明镜;王星星;;[J];测绘通报;2012年S1期
宋茂忠;[J];南京航空航天大学学报;2000年05期
高端阳;李厚朴;段慧娟;;[J];海洋测绘;2017年02期
中国重要会议论文全文数据库
于军;邓明镜;王星星;;[A];第四届“测绘科学前沿技术论坛”论文精选[C];2012年
中国硕士学位论文全文数据库
姜宁;[D];大连海事大学;2008年
&快捷付款方式
&订购知网充值卡
400-819-9993小生境（Niche）：来自于生物学的一个概念，是指特定环境下的一种生存环境，生物在其进化过程中，一般总是与自己相同的物种生活在一起，共同繁衍后代。例如，热带鱼不能在较冷的地带生存，而北极熊也不能在热带生存。把这种思想提炼出来，运用到优化上来的关键操作是：当两个个体的海明距离小于预先指定的某个值(称之为小生境距离)时，惩罚其中适应值较小的个体。海明距离（Hamming Distance）：在信息编码中，两个合法代码对应位上编码不同的位数称为码距，又称海明距离。例如，1从第一位开始依次有第一位、第四、第五位不同，则海明距离为3。
如果觉得有帮助，用Google学术搜索应该能找到这篇，在www.sciencedirect.com上也可以找到。读书笔记如下：
===========================================华丽丽的分割线=========================================1. Introduction
两种比较普遍的处理多目标GA的方法：
把所有目标合并成一个目标函数，或者给某个集合只分配一个目标函数，以加权法为例，缺点是很难精确地确定权重，权重分配上一点点的不同可能导致相差很大的解；确定Pareto解集或其有代表性的子集。2. Multi-objective optimization formulation有些问题的Pareto解集很大（可能无界），有效的方法是去找能代表Pareto解集的一系列解（the best-known Pareto set），尽可能满足3个要求：尽可能接近真正的Pareto解集，并且理想地应当是Pareto解集的子集；均匀分布；能捕捉到Pareto解集的边界，也就是能到达目标函数的极端。3. Genetic algorithms交叉：让种群收敛到比较好的表现型；变异：向种群中注入基因的多样性，防止搜索过程太快地收敛到局部最优。4. Multi-objective GA通常，不同的多目标GA的差异体现在三个方面：适应度分配过程、精英主义（elitism）和多样化方法。5. Design issues and components of multi-objective GA
5.1 Fitness functions5.1.1 Weighted sum approachesMBGA：每个个体在计算目标函数值时，各目标函数的权重 w={ w1, w2, ... , wk } 都不同；RWGA：w={ w1, w2,…, wk } 是随机的。优点——容易实现；缺点：如果Pareto解集是非凸的，不是所有的Pareto解都能被搜到。
5.1.2 Altering objective functions
VEGA：并列选择法。优点——容易实现，与单目标GA的效率差不多；缺点：种群容易很快地收敛在某一目标上特别好但在其他目标上比较差的解。
5.1.3 Pareto-ranking approaches
某一代中，依据目标函数值的排名（而不是目标函数值本身）给每个个体分配一个适应度。NSGA-II：在目标函数空间里，惩罚那些被高密度Pareto解集支配的个体，如：(b)个体i；SPEA：在目标函数空间里，给那些在不具有代表性区域内的个体分配更好的适应度，如：(c)个体a，有助于得到更加广泛、更加全局分布的Pareto解集；Accumulated ranking density strategy ：惩罚种群的冗余，即高密度区域的个体，如：(d)个体i、l、n。
5.2. Diversity: fitness assignment, fitness sharing, and niching
5.2.1 Fitness sharing
在归一化的目标空间，计算某一代个体之间的欧几里得距离（Euclidean distance） -& 根据欧几里得距离，计算小生境数（niche count） -& 每个个体的修正适应度=它的适应度/小生境数。
优点：目标空间里，密度高的区域内的个体会有较高的小生境数，适应度会因此变小，从而限制了在某个小生境内的快速繁殖；缺点：不好确定小生境的大小（niche size），计算的难度大。
MOGA（保持多样性的同时逼近真正的Pareto解集的算法），它计算适应度过程：用NSGA-II的方法计算每个个体的排名 -& 根据排名计算初始的适应度 -& 计算小生境数 -&每个个体的共享适应度（shared fitness value）=它的适应度/小生境数 -& 计算归一化的适应度。
SPEA2：一个个体的密度定义为离它最近的第k个个体与它的距离的倒数，个体的密度与它的小生境相似，并且确定参数k比确定小生境的大小更直接。
5.2.2 Crowding distance
NSGA-II：为某一代的个体排序并识别非支配解集 -& 计算每个个体针对每个目标函数的拥挤距离（crowding distance） -&计算个体所有目标函数的拥挤距离和，也就是该个体的拥挤距离。
优点：不通过适应度保持多样性，不需要自己确定参数（比如小生境的大小、k）。通常用作确定最后的选择个体。
5.2.3 Cell-based density
目标函数空间被分为K维房间（cell），每个房间里的个体数就是该房间里每个个体的密度，密度被用来保持多样性。
PESA：E是记录非支配解的仓库，某一代的个体都要根据是否被E中的个体支配，决定是否进入E，从而不断更新E，然后从E中选出密度小的个体做交叉变异。
PESA-II：选择的是房间，而不是个体。
RDGA：把目标函数空间分为许多K维房间 -& 更新每个目标函数的房间尺寸 -& 识别每个个体属于哪个房间，计算密度 -& 按照NSGA方法计算个体的排名 -& 把排名靠前和密度低的个体放到配对池中（两目标） -& 配对池中，被选择的父代只与所在房间/相邻房间中最好的个体交叉，且不允许被父代支配的个体进入房间，如果父代被自己的子代支配，就用子代代替父代。
优点：掌握了全局的密度分布，根据全局的密度搜索会向着密度小的区域进行；比小生境和计算周围密度的方法效率更高。
5.3 Elitism
精英主义（Elitism）的思想就是最好的个体应当保存到下一代，多目标GA有两种方法确保精英主义：
在群体里保存精英个体；另外存储精英个体，并且把它们重新引入到群体中。5.3.1 Strategies to maintain elitist solutions in the population某一代的非支配个体直接复制到下一代，对其余个体选择交叉变异繁殖子代，填充到下一代。缺点：如果某一代的非支配个体和产生的子代数目和，超过了群体大小的限制，这种方法就不行了。下面这些方法中，群体大小是一个重要的参数。解决方法一：群体中只包含非支配个体，如果群体中个体数目达到上限，就移除（上限-下限）个个体，为了保持多样性，移除方法是对比两个随机选择的个体的小生境数，将小生境数大的个体从群体中移除。解决方法二（NSGA-II）：对某一代的个体做交叉变异得到子代 -& 这一代和子代合并到一个集合中 -& 将集合中的个体分为k个等级的非支配解集 { F1, F2, …, Fk }
-& 计算每个个体的拥挤距离（按照5.2.2的方法） -& 从F1开始复制到下一代中，直到Ft加入下一代时，下一代的个体数刚好达到或者超过限制，如果超过了限制，就从Ft中选择拥挤距离小的个体填充到下一代。
5.3.2 Elitism with external populations
用E另外存储精英个体时，有两个关键问题：E中保存哪些个体：E保存非支配个体，且是不断更新；E有多大：通过剪枝来控制E的大小NE。SPEA：把E中的个体分配到一个簇（cluster）ci中，所有簇构成C={ c1, c2, …, cM} -& 计算各个簇之间的距离 -& 把两个距离最近的簇合并成一个簇，重复前述步骤直到簇的个数&=N -& 从每个簇中选择到该簇中其他个体距离最近的个体，构成新的E，移除E中的其他个体。SPEA2：把某一代群体Pt和Et合并 -& 计算其中每个个体的适应度 -& 把合并的集合全部复制到E(t+1)中，有两种情况：如果| E(t+1)|&NE，从E(t+1)移除一部分个体；如果| E(t+1)|，从合并的集合中再复制最好的个体填充。
5.4 Constraint handling
现实生活中的问题通常有一些限制条件，单目标GA从四个方面处理限制条件：丢弃不可行解；用惩罚函数降低不可行解的适应度；构造算子使得只繁殖可行解；把不可行解转变为可行解。上述第二种方法是最常用的，但不能直接运用到多目标GA中，因为在多目标GA中，适应度是根据一个个体的非支配排名，而不是他的目标函数值分配的。解决方法是从群体中选择两个个体x和y，有以下三种情况：一个可行一个不可行：可行的胜出；x, y都不可行：从群体中的不可行解里随机选择一组构成集合C，计算x, y以及C中所有个体的不可行性，对比x, y和C中最好个体的不可行性，如果x, y一个优于一个劣于最好个体，优于的个体胜出，如果x, y都优于/劣于最好个体，小生境数小的胜出；x, y都可行：从群体中的可行解里随机选择一组构成集合C，如果x, y一个支配C一个至少被C中的一个个体支配，前者胜出，否则小生境数小的胜出。缺点：计算复杂度和增加的变量（例如，C的大小和小生境的大小），但可以通过调整减少。Constraint-domination：个体x限制支配个体y，当满足x可行y不可行/x, y均不可行但x违背的限制条件更少/x, y均可行且x支配y。Constraint tournament method：按照Constraint-domination的规则，重新定义非支配解集{ F1, F2, …, Fk }为非限制支配解集，执行“选择”步骤时，对任意两个个体x, y，如果x所在Fi和y所在Fj满足i，则x胜出，如果x, y在同一解集中，根据小生境数或拥挤距离决定胜者。优点：变量少，容易融合到多目标GA中。Dominance-based tournament selection：个体x限制支配个体y，当满足对每个限制条件x的违背少于或与y相等，且至少有一个限制条件，x的违背少于y。
5.5 Parallel and hybrid multi-objective GA
精英主义和多样性的保持机制能提高多目标GA的效果，但是通常都会提高计算复杂度和存储空间，并行和分布式的GA是一种解决方法。在单目标GA中，本地搜索算法的复合是最近用到的一种方法，本地搜索算法是：从一个初始个体开始 -& 用简单的扰动法则产生一些相邻的解 -& 如果相邻的解中有个体优于初始个体，替代。优点：如果初始个体附近的解空间是凸的，查找局部最优的效果很好。关键点：选择初始个体；有很多非支配个体时，识别相邻解中的最优解。6. Multi-objective GA for reliability optimization多目标GA的运用7. Conclusions这篇论文关注各种多目标GA的构成要素和实现时遇到的突出问题；Pareto解集需要被削减为一个有代表性的小集合，要使计算保持在合理的层次必须控制它的大小；实现时必须考虑计算的复杂度，根据问题定制一些东西，例如，边界、假设、具体的计算方法等。
遗传算法小生境技术简介
生物学上，小生境是指特定环境下的一种组织结构。在自然界中，往往特征，形状相似的物种相聚在一起，并在同类中交配繁衍后代。在SGA 中，交配完全是随机的，在进化的后期，大量的个体集中于某一极值点上，在用遗...
多目标优化系列（六）SPEA
Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach
多目标优化问题概述
图片不清楚请看多目标问题详解：多目标问题详解
定义：若干冲突或相互影响条件约束下在给定区域内寻找尽可能的最优解（非劣解）。
关键词：条件约束，折中最优解（解并非唯一是与单目标优化问题的本质区别） ...
多目标优化详解
欢迎大家访问我的网站发现更多内容omegaxyz.com
多目标优化问题详解
生活中 ,许多问题都是由相互冲突和影响的多个目标组成。人们会经常遇到使多个目标在给定区域同时尽可能最佳的...
多目标优化系列（三）MOEA/D
MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition
中文链接：https://wenku.baidu.c...
小生境思想在多目标优化算法中的运用
最近在写多目标优化算法的程序，最初主要还是借鉴别人的思想。如NSGAII，算法出自《A fast and elitist multiobjective genetic algorhm》，一...
多目标进化算法(MOEA)概述
多目标进化算法系列
1. 多目标进化算法(MOEA)概述
2. 多目标优化-测试问题及其Pareto前沿
3. 多目标进化算法详述-MOEA/D与NSGA2优劣比较
4. 多目标进化算...
多目标优化
多目标优化
没有更多推荐了，能通俗解释下NSGA3算法吗。？ - 知乎知乎 - 有问题上知乎50被浏览<strong class="NumberBoard-itemValue" title="分享邀请回答赞同 5 条评论分享收藏感谢收起基于FA-NSGA分扭传动系统的均载和轻量化优化设计--《航空动力学报》2014年09期
基于FA-NSGA分扭传动系统的均载和轻量化优化设计
【摘要】：以提高均载性能和轻量化为目标对某分扭传动系统进行了多目标优化设计.建立了分扭传动的非线性动力学模型,通过计算不同输入功率和输入转速下的均载系数,衡量分扭传动系统均载性能.以分扭传动系统参数为设计变量,考虑多工况条件,建立了以均载系数和质量最小为目标函数的多目标优化模型.为了提高计算效率,提出了具有适应值预测机制的非支配排序遗传算法(FA-NSGA).利用3个基准函数对FA-NSGA进行收敛性和有效性的测试.结果表明:FA-NSGA对于3个测试函数均能获得满意的最优解,并且都能减少60%以上的真实适应值计算次数.采用FA-NSGA对实例进行优化求解,在得到的Pareto最优解中选取了一组满意的设计参数,该设计结果与参照方案相比均载系数降低了0.05,分扭传动系统质量减少了3.57kg.
【作者单位】：
【分类号】：TH132
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【相似文献】
中国重要会议论文全文数据库
颜伏伍;王洪建;田韶鹏;袁智军;;[A];湖北省内燃机学会2009年学术年会论文集[C];2009年
吕志军;杨建国;宁波;娄文斌;;[A];全国先进制造技术高层论坛暨第十届制造业自动化与信息化技术研讨会论文集[C];2011年
中国博士学位论文全文数据库
曾强;[D];重庆大学;2010年
王晓娟;[D];华中科技大学;2011年
李光;[D];天津大学;2012年
中国硕士学位论文全文数据库
王洪建;[D];武汉理工大学;2010年
杨娟;[D];南昌大学;2013年
周鑫;[D];浙江大学;2013年
李芳振;[D];电子科技大学;2012年
马威;[D];华东理工大学;2011年
李传鹏;[D];济南大学;2013年
王录;[D];中国科学院研究生院（工程热物理研究所）;2010年
刘江;[D];电子科技大学;2012年
牟瑛;[D];重庆工商大学;2011年
陈雄兵;[D];重庆大学;2012年
&快捷付款方式
&订购知网充值卡
400-819-9993http://www.zhihu.com/question/
北京大学的Online Judge。POJ上面的题目有点老了，但好处是做的人多，经典算法题多，解题报告也多，适合上手。-
浙江大学的Online Judge。ZOJ用的不多，但为数不多的几次体验好像都还可以，值得尝试。-
北京大学的Online Judge。POJ上面的题目有点老了，但好处是做的人多，经典算法题多，解题报告也多，适合上手。-
浙江大学的Online Judge。ZOJ用的不多，但为数不多的几次体验好像都还可以，值得尝试。-
杭州电子科技大学的OJ。杭电OJ在近几年取代了POJ，成为是目前国内最主流的OJ。它的题目丰富，难度梯度合理，广受全国各大高校的青睐。每年也会有大大小小的比赛挂在杭电的OJ上举办，去年的亚洲区网络赛也是在这上面做的。由此可见其在国内广大ACMer心目中的地位。也正因为如此，网上hdu的解题报告也很多，适合个人进阶训练。-
西班牙Valladolid大学的Online Judge。是最古老也是全世界最知名的Online Judge，题库有详细的分类:如世界总决赛题目，刘汝佳的题目等等。题目目类型非常广泛。绝大部分的题目难度偏易，适合初学者磨练程序设计。-
URAL是一个俄罗斯的在线题库。里面的题目相比国内一些OJ来说颇有些难度，我们学校集训队老队员喜欢拿这里的题出给新队员做，可见有一定的进阶作用。-
SPOJ是波兰最为出色的Online Judge之一，界面和谐，题目类型也非常丰富，适合有一定基础的选手练习，对高手而言也是个提高能力的良好平台。传说君临天下的楼教主刷完了这个OJ？（更正：楼教主刷完的是SGU，感谢
指正）更多介绍见博客：。-
USACO是美国中学生的官方竞赛网站、美国著名在线题库，专门为信息学竞赛选手准备；做题方式模拟正式比赛，采用标准测评机、文件输入输出、直接提交程序源文件的测评方式；网站的Training题目全面，是学习信息学不可不知的网站，每年， 都会参考上面的题目；每道题附有详细题解，可查看测试数据和运行结果，便于调试、发现错误并改正。采用章节递进的层次结构，由易到难，讲授知识、练习编程结合，题目必须依次完成，避免了只挑简单题做的行为；各章节犹如一本竞赛辅导书，形成了一个鲜明的知识结构，利于OI初学者和高手逐步提高水平，充分学习信息学各方面知识，避免偏颇。（来源：）-
之前上SGU一直是404，所以不敢贴上来。现在亲测能上了就也放上来给大家看看吧。这个是货真价实的楼教主刷完的OJ。楼教主为什么要刷这个OJ而不刷这个回答里的其他OJ呢？因为这个OJ确实适合提升水平，应该跟Ural, SPOJ的难度相当。另外就不太了解了，在我心目中，SGU, Ural, SPOJ都适合区域赛冲金以及毕业想去Google等顶级公司的ACMer/Coder训练，三者区别不大。-
Codefores是俄罗斯的一个算法竞赛网站，由
创办和维护。Codeforces主要强调的是算法竞赛，每隔1个礼拜左右就会有定期的线上比赛举行，其题库也是由每场比赛的题目一场场积累下来的。相比上面几个以题库为核心的OJ，Codeforces的算法竞赛比较适合锻炼自己的临场发挥和压力下编程能力。-
华中科技大学的Online Judge。hustOJ也和主流的其他OJ一样有着丰富的题库。但它主要的用处，是它所提供的这么一个叫做vjudge的东西，全称叫做Virtual Judge。通过vjudge，你可以从各大OJ、包括但不限于上述的所有OJ中直接抽取题目，利用这些题目创建一个属于你自己的比赛。非常适合专题训练、日常集训以及小伙伴们一起比赛切题玩。-
与很多OJ不同，leetcode是一个主要面向面试者的OJ (LeetCode OJ is a platform for preparing technical coding interviews)。上面的题目不多，目前只有152道，很多都是许多大公司的面试题目。题目类型偏基础，基本不会考察复杂的算法，很多都是对基础知识的应用，难度与topcoder div1 250或codeforces div1 A题难度相当。如果是希望练习编程基础或准备公司面试的话非常推荐此OJ（感谢室友/集训队大神/CMU准硕士
同学提供Leetcode介绍 (1/1/2015更新：室友拿了google的offer不去CMU了)）。-
感谢评论区 建议，添加BZOJ。
刷题也就这么点地方1Leetcode鼎鼎大名的Leetcode，据不完全统计在上面被刷过的题可以围绕地球三圈。（没说赤道哈，就是这么严谨。）总之，很多国内外的码农在上面刷题。难度从easy到hard都有，而且覆盖面极广。现在还增加了数据库和shell，相匹配的论坛也可以多看看。很锻炼和国外码农沟通的能力，对于以后去混Github也有好处。特点：各种语言支持很广泛，题型覆盖很广，测试数据集较弱。2Codility同样一家著名的国外刷题网站。和Leetcode不同，它是专门帮各大软件公司笔试用的，只是副业提供了一些面试题和挑战。但即使是训练模式都非常经典，很值得一做。而且测试数据集提供的非常完善，总能让你有想不到的边界情况。Take our free programming lessons特点：很接近面试题的风格，训练模式也基本够用。3Lintcode可以称作中文版本的Leetcode，个人感觉最高难度比Leetcode高一些。这两个类似的网站，可以配套来刷。每个刷一遍，也能保持新鲜感。特点：中文支持很好，和Leetcode有一部分题类似，可以和九章算法课程配合使用。4Hihocoder来自于原北京大学POJ开发团队，网站一直在进步。最早是微软的在线笔试网站，现在网易也使用它进行在线笔试。题目侧重于较难题目，风格很像ACM比赛，要自己注意数据集的输入输出。特点：每周一道算法题极难又有趣，可以用来扩展面试题思路。而且是网易、微软的在线笔试网站，有机会需要多练习。5CC150这不是网站，这是一本书。全称Cracking the coding interview，是国外找工作的神书，而且的确写的很好。里面除了算法题，还有计算机基础知识等内容，很不错。适合想去外企的人仔细阅读，而且最新版已经比150题多了。总之，外企必备！特点：外企必备！外企必备！外企必备！想去外企的人，多看看书的配套答案也是好的结论：最后，经过公众号作者小分队的讨论，根据不同方向的工作，我们建议按照以下方式刷题：国企、银行、科研单位Leetcode简单、中等难度最好刷一遍，有时间再过一遍思路。创业公司Leetcode全部难度上机刷一遍，然后把不会的题纸上在重新写一下。国内互联网Leetcode全部难度上机刷一遍，纸上再写一遍。同时尽量涉及难度较高的平台（Codility），或者多去几家公司面试，以赛代练。国内外企Leetcode至少全难度刷一遍，CC150纸上写一遍。想提高Microsoft/Google等在线笔试通过率的，多去玩玩Hihocoder等在线笔试平台。外企总部Leetcode困难程度烂熟于心，尽量达到ACM入门标准，甚至稍高一点比较有把握。最后欢迎大家关注我们的公众号。 看一群在IT圈混的人的碎碎念。
作者：程序员的下班生活链接：http://www.zhihu.com/question//answer/来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
阅读(...) 评论()