請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/88782
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 于天立 | zh_TW |
dc.contributor.advisor | Tian-Li Yu | en |
dc.contributor.author | 廖勗辰 | zh_TW |
dc.contributor.author | Hsu-Chen Liao | en |
dc.date.accessioned | 2023-08-15T17:45:54Z | - |
dc.date.available | 2023-11-09 | - |
dc.date.copyright | 2023-08-15 | - |
dc.date.issued | 2023 | - |
dc.date.submitted | 2023-08-07 | - |
dc.identifier.citation | F. Altiparmak, M. Gen, L. Lin, and T. Paksoy. A genetic algorithm approach for multi-objective optimization of supply chain networks. Computers & industrial engineering, 51(1):196–215, 2006.
F. Barahona, M. Grötschel, M. Jünger, and G. Reinelt. An application of combinatorial optimization to statistical physics and circuit layout design. Operations Research, 36(3):493–513, 1988. T. K. Biswas, A. Abbasi, and R. K. Chakrabortty. An improved clustering based multi-objective evolutionary algorithm for influence maximization under variablelength solutions. Knowledge-Based Systems, 256:109856, 2022. P. A. Bosman. The anticipated mean shift and cluster registration in mixture-based EDAs for multi-objective optimization. In Proceedings of the 12th annual conference on Genetic and evolutionary computation, pages 351–358, 2010. P. A. Bosman and D. Thierens. Linkage neighbors, optimal mixing and forced improvements in genetic algorithms. In Proceedings of the 14th annual conference on Genetic and evolutionary computation, pages 585–592, 2012. P. A. Bosman and D. Thierens. More concise and robust linkage learning by filtering and combining linkage hierarchies. In Proceedings of the 15th annual conference on Genetic and evolutionary computation, pages 359–366, 2013. P.-L. Chen, C.-J. Peng, C.-Y. Lu, and T.-L. Yu. Two-edge graphical linkage model for DSMGA-II. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 745–752, 2017. K. Deb and D. E. Goldberg. Sufficient conditions for deceptive and easy binary functions. Annals of mathematics and Artificial Intelligence, 10:385–408, 1994. K. Deb and H. Jain. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints. IEEE transactions on evolutionary computation, 18(4):577–601, 2013. K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, 6(2):182–197, 2002. G. R. Harik, F. G. Lobo, and K. Sastry. Linkage learning via probabilistic modeling in the extended compact genetic algorithm (ecga). In Scalable optimization via probabilistic modeling, pages 39–61. Springer, 2006. H. Ishibuchi, N. Akedo, and Y. Nojima. A study on the specification of a scalarizing function in MOEA/D for many-objective knapsack problems. In Learning and Intelligent Optimization: 7th International Conference, LION 7, Catania, Italy, January 7-11, 2013, Revised Selected Papers 7, pages 231–246. Springer, 2013. H. Ishibuchi, N. Tsukamoto, and Y. Nojima. Evolutionary many-objective optimization: A short review. In 2008 IEEE congress on evolutionary computation (IEEE world congress on computational intelligence), pages 2419–2426. IEEE, 2008. L. Jenkins. A bicriteria knapsack program for planning remediation of contaminated lightstation sites. European Journal of Operational Research, 140(2):427–433, 2002. N. Khan, D. E. Goldberg, and M. Pelikan. Multi-objective Bayesian optimization algorithm. In Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation, pages 684–684, 2002. M. M. Kostreva, W. Ogryczak, and D. W. Tonkyn. Relocation problems arising in conservation biology. Computers & Mathematics with Applications, 37(4-5):135–150, 1999. N. H. Luong and P. A. Bosman. Elitist archiving for multi-objective evolutionary algorithms: To adapt or not to adapt. In International Conference on Parallel Problem Solving from Nature, pages 72–81. Springer, 2012. N. H. Luong, H. La Poutré, and P. A. Bosman. Multi-objective gene-pool optimal mixing evolutionary algorithms. In Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, pages 357–364, 2014. N. H. Luong, H. La Poutré, and P. A. Bosman. Multi-objective gene-pool optimal mixing evolutionary algorithm with the interleaved multi-start scheme. Swarm and Evolutionary Computation, 40:238–254, 2018. R. T. Marler and J. S. Arora. Survey of multi-objective optimization methods for engineering. Structural and multidisciplinary optimization, 26:369–395, 2004. A. Mohammadi and M. Saraee. Finding influential users for different time bounds in social networks using multi-objective optimization. Swarm and evolutionary computation, 40:158–165, 2018. R. Olivares, F. Muñoz, and F. Riquelme. A multi-objective linear threshold influence spread model solved by swarm intelligence-based methods. Knowledge-Based Systems, 212:106623, 2021. M. Olsthoorn and A. Panichella. Multi-objective test case selection through linkage learning-based crossover. In International Symposium on Search Based Software Engineering, pages 87–102. Springer, 2021. M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 511–518, 2001. M. Pelikan, D. E. Goldberg, and K. Sastry. Bayesian optimization algorithm, decision graphs, and Occam's razor. In Proceedings of the Genetic and Evolutionary Computation Conference, volume 519526, 2001. M. Pelikan, K. Sastry, and D. E. Goldberg. Multiobjective hboa, clustering, and scalability. In Proceedings of the 7th annual conference on Genetic and evolutionary computation, pages 663–670, 2005. J. F. Robles, M. Chica, and O. Cordon. Evolutionary multiobjective optimization to target social network influentials in viral marketing. Expert systems with applications, 147:113183, 2020. M. J. Rosenblatt and Z. Sinuany-Stern. Generating the discrete efficient frontier to the capital budgeting problem. Operations Research, 37(3):384–394, 1989. R. A. Rossi and N. K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. A. Sheikhahmadi and A. Zareie. Identifying influential spreaders using multiobjective artificial bee colony optimization. Applied Soft Computing, 94:106436, 2020. M. G. C. Tapia and C. A. Coello. Applications of multi-objective evolutionary algorithms in economics and finance: A survey. In 2007 IEEE congress on evolutionary computation, pages 532–539. IEEE, 2007. D. Thierens. The linkage tree genetic algorithm. In International Conference on Parallel Problem Solving from Nature, pages 264–273. Springer, 2010. D. Thierens and P. A. Bosman. Optimal mixing evolutionary algorithms. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, pages 617–624, 2011. D. A. Van Veldhuizen and G. B. Lamont. Multiobjective optimization with messy genetic algorithms. In Proceedings of the 2000 ACM symposium on Applied computingVolume 1, pages 470–476, 2000. S. Verma, M. Pant, and V. Snasel. A comprehensive review on nsga-ii for multiobjective combinatorial optimization problems. IEEE Access, 9:57757–57791, 2021. R. A. Watson, G. S. Hornby, and J. B. Pollack. Modeling building-block interdependency. In International Conference on Parallel Problem Solving from Nature, pages 97–106. Springer, 1998. T.-L. Yu and D. E. Goldberg. Dependency structure matrix analysis: Offline utility of the dependency structure matrix genetic algorithm. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), pages 355–366, 2004. T.-L. Yu, A. A. Yassine, and D. E. Goldberg. An information theoretic method for developing modular architectures using genetic algorithms. Research in Engineering Design, 18:91–109, 2007. Q. Zhang and H. Li. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on evolutionary computation, 11(6):712–731, 2007. E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: Improving the strength Pareto evolutionary algorithm. TIK-report, 103, 2001. E. Zitzler and L. Thiele. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE transactions on Evolutionary Computation, 3(4):257–271, 1999. J. B. Zydallis and G. B. Lamont. Explicit building-block multiobjective evolutionary algorithms for npc problems. In The 2003 Congress on Evolutionary Computation, 2003. CEC’03., volume 4, pages 2685–2695. IEEE, 2003. | - |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/88782 | - |
dc.description.abstract | 多目標基因池最佳混合進化式演算法 (MO-GOMEA) 是一種強大且無需參數的基於模型的基因演算法,擅長解決多目標組合優化問題。這篇研究論文從雙目標優化問題獲取啟發,進而提出自適應捐贈者選擇混合(ADSM)機制,此機制的構思是基於目標間錯綜複雜的相互關係。此機制設計特別針對群集導向和菁英導向混合對於目標在雙目標優化中的一致性、孤立性和不一致性改善的影響進行深入探討。將ADSM整合到MO-GOMEA中後,產生了一個新的變體,即ADSM-MO-GOMEA。對多種基準問題的實證評估顯示,ADSM-MO-GOMEA在反轉世代距離(IGD)和前沿佔用率(FO)兩個指標上均優於原始的MO-GOMEA。在ADSM-MO-GOMEA超越MO-GOMEA的問題中,我們觀察到IGD指標平均提升約10%,且在多目標背包問題的FO指標上也有顯著的提升。此外,本研究將範疇進一步擴大至涵蓋三至五個目標的問題,並考慮群集導向與菁英導向混合在改善目標一致性上的差異。在這種情況下,一致性的程度由顯示改善的目標數量決定。此延伸研究的實證結果揭示了,在處理具有更多目標的優化問題時,將一致性概念與修訂的ADSM結合起來將能有效改進原始MO-GOMEA的演化效率。 | zh_TW |
dc.description.abstract | The multi-objective gene-pool optimal mixing evolutionary algorithm (MO-GOMEA) is a powerful, parameterless genetic algorithm that effectively solves multi-objective combinatorial optimization problems. Drawing insights from bi-objective optimization, this study introduced the adaptive donor selection mixing (ADSM) mechanism, devised in view of the intricate inter-relationship among objectives. It particularly focuses on the effects of cluster-guided and elitist-guided mixing on three types of improvements in objectives: coherent, solitary, and incoherent. The integration of ADSM into MO-GOMEA leads to the development of ADSM-MO-GOMEA. Empirical assessments on varied benchmark problems underscore that ADSM-MO-GOMEA outperforms its predecessor MO-GOMEA, excelling in both inverted generational distance (IGD) and front occupancy (FO) metrics. An average enhancement of about 10\% in the IGD metric is observed where ADSM-MO-GOMEA outperforms the original, alongside a significant boost in the FO metric for the multi-objective knapsack problem. The research scope is further extended to tackle problems with three to five objectives, factoring in the impact of the coherency of improvement across objectives when employing cluster-guided and elitist-guided mixing. In this context, the degree of coherence is determined by the count of objectives that exhibit improvement. The empirical results from this broader study underscore the advantages of embedding the coherence concept within the refined ADSM in addressing optimization problems with a greater count of objectives. | en |
dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2023-08-15T17:45:54Z No. of bitstreams: 0 | en |
dc.description.provenance | Made available in DSpace on 2023-08-15T17:45:54Z (GMT). No. of bitstreams: 0 | en |
dc.description.tableofcontents | Acknowledgements i
摘要 iii Abstract v Contents vii List of Figures xi List of Tables xv Chapter 1 Introduction 1 Chapter 2 Background 5 2.1 Multi-objective Combinatorial Optimization 5 2.1.1 Problem Formulation 6 2.1.2 Performance Metrics 8 2.2 Approach to Multi-objective Combinatorial Optimization 9 2.2.1 Multi-objective Genetic Algorithm 9 2.2.2 Multi-objective Model-building Genetic Algorithm 10 2.3 MO-GOMEA 10 2.3.1 Elitist Archive 11 2.3.2 K-leader-means Clustering 12 2.3.3 Interleaved Multi-start Scheme 13 2.3.4 Recombination 13 2.4 High-dimensional Multi-objective Combinatorial Optimization Benchmark Problems 18 2.4.1 Zeromax-onemax 18 2.4.2 Trap5-inverse Trap5 19 2.4.3 Leading Ones Trailing Zeros 19 2.4.4 Multi-objective Knapsack 20 2.4.5 Multi-objective Maxcut 21 Chapter 3 The Proposed ADSM-MO-GOMEA 23 3.1 Investigation on Inter-relationship among Objectives 23 3.2 Correlation between Building Blocks and Multi-objective Optimization 25 3.3 Cluster-guided Mixing and Elitist-guided Mixing 27 3.4 Evolving Regions 30 3.5 Receiver-aware Donor Selection 32 3.6 Self-Adaptive Switching Based on Temporal Change of Objective Inter-relationships 37 3.7 ADSM-MO-GOMEA 42 Chapter 4 Experiments and Results 45 4.1 Experiment Settings and Performance Evaluation 45 4.2 Results and Discussions 46 4.2.1 Comparison on Scalable Benchmarks 47 4.2.2 Comparison on MO Knapsack 47 4.2.3 Comparison on MO Maxcut 49 Chapter 5 Beyond Two Objectives 53 5.1 Test Problems 53 5.2 Modification of ADSM-MO-GOMEA 55 5.3 Experiment Settings 58 5.4 Empirical Results 60 5.4.1 Comparison on Three-objective NPC Problems 60 5.4.2 Comparison on Five-objective MO Knapsack 63 5.4.3 Comparison on MIMP 64 Chapter 6 Conclusion 67 References 69 | - |
dc.language.iso | en | - |
dc.title | 探討多目標組合優化中目標間的交互關係:多目標基因池最佳混合進化式演算法的加強變體 | zh_TW |
dc.title | Investigation on Inter-relationship among Objectives for Multi-objective Combinatorial Optimization: an Enhanced Variant of MO-GOMEA | en |
dc.type | Thesis | - |
dc.date.schoolyear | 111-2 | - |
dc.description.degree | 碩士 | - |
dc.contributor.oralexamcommittee | 陳穎平;雷欽隆 | zh_TW |
dc.contributor.oralexamcommittee | Ying-Ping Chen;Chin-Laung Lei | en |
dc.subject.keyword | 多目標最佳化,基因遺傳演算法,建構模塊,供體選擇, | zh_TW |
dc.subject.keyword | Multi-objective optimization,Model building,Genetic algorithm,Donor selection, | en |
dc.relation.page | 74 | - |
dc.identifier.doi | 10.6342/NTU202303309 | - |
dc.rights.note | 同意授權(全球公開) | - |
dc.date.accepted | 2023-08-09 | - |
dc.contributor.author-college | 電機資訊學院 | - |
dc.contributor.author-dept | 電機工程學系 | - |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-111-2.pdf | 4.47 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。