PL Zastosowanie miar niepodobieństwa struktur 3D do zwiększenia efektywności projektowania ewolucyjnego

angielski

EN Evolutionary algorithms are a powerful tool for solving hard optimization problems, such as designing three-dimensional structures for various applications. Unlike human designers, these algorithms have the potential to explore an infinite solution space more extensively without requiring expert knowledge. However, the problem of evolutionary design, often characterized by a multimodal and rugged fitness landscape, still poses a challenge, and there is still room for improvement in optimization methods applied to it. This work explores the possibility of enhancing the effectiveness of evolutionary search by utilizing phenetic dissimilarity measures for 3D structures. Developing a dissimilarity measure for 3D structures is a challenging problem in itself since there is no ground truth for the dissimilarity values. In this work, various dissimilarity measures are implemented and compared, including genotype-based, morphology graph-based, shape descriptor-based, and spatial distribution-based measures. Additionally, human perception of similarity is investigated as a potential reference point. The implemented measures are used to test the global convexity of the fitness landscape using the fitness-distance correlation (FDC) analysis in four optimization tasks, using three different genetic representations. In some of the cases examined, the fitness-distance correlation is negative, which may imply a global convexity of the fitness landscape. With the aim to facilitate the effective search of the solution space, enhanced genetic operators are introduced, including Targeted Sequential Mutation (TSM), Distance Minimizing Crossover (DSX), Equidistance Minimizing Crossover (EMX), Distance Preserving Crossover (DPX), and Similarity-Based Crossover (SBX). The goal of these operators is to adjust the distance between parent and offspring solutions according to the selected dissimilarity measure. The performance of these operators is evaluated against the standard ones in a series of computational experiments. The TSM operator outperforms the standard mutation operator in most cases, whereas the proposed crossover operators achieve results comparable to the standard ones. In the next strand of work, dissimilarity measures are applied in diversity maintenance techniques, which are methods for encouraging broader exploration of the solution space. The study compares the standard evolutionary algorithm with niching (local and global variants), novelty search (local and global variants), and the Non-dominated Sorting Genetic Algorithm II (NSGA-II), utilizing different dissimilarity measures. The analysis of the results reveals how different algorithms and dissimilarity measures influence the outcome of the evolution in terms of fitness and heterogeneity of the solutions.

PL Algorytmy ewolucyjne są skutecznym narzędziem do rozwiązywania trudnych problemów optymalizacyjnych, takich jak projektowanie trójwymiarowych struktur dla różnorakich zastosowań. W przeciwieństwie do ludzkich projektantów, algorytmy te są w stanie szerzej eksplorować nieskończoną przestrzeń rozwiązań, nie wymagając przy tym wiedzy eksperckiej. Jednak problem projektowania ewolucyjnego, często charakteryzujący się multimodalnym i nieregularnym krajobrazem przystosowania, nadal stanowi wyzwanie i wciąż istnieje pole do poprawy stosowanych do niego metod optymalizacji. W niniejszej pracy zbadano możliwość zwiększenia skuteczności przeszukiwania ewolucyjnego poprzez wykorzystanie miar niepodobieństwa fenetycznego dla struktur 3D. Opracowanie miary niepodobieństwa dla struktur 3D jest samo w sobie trudnym problemem, ponieważ nie jest znana obiektywna wartość niepodobieństwa. W niniejszej pracy zaimplementowano i porównano różne miary niepodobieństwa, w tym oparte na genotypie, grafie reprezentującym morfologię, deskryptorach kształtu i rozkładzie przestrzennym. Dodatkowo zbadano ludzkie postrzeganie podobieństwa jako potencjalny punkt odniesienia. Zaimplementowane miary są wykorzystywane do testowania globalnej wypukłości krajobrazu przystosowania przy użyciu analizy korelacji pomiędzy przystosowaniem a odległością do optimum (fitness-distance correlaction, FDC) w czterech zadaniach optymalizacyjnych, przy użyciu trzech różnych reprezentacji genetycznych. W niektórych z badanych przypadków korelacja wartości funkcji przystosowania i odległości jest ujemna, co może sugerować globalną wypukłość krajobrazu przystosowania. W celu usprawnienia efektywności przeszukiwania przestrzeni rozwiązań, zaproponowano ulepszone operatory genetyczne, w tym Celowaną Mutację Sekwencyjną (Targeted Sequential Mutation, TSM), Krzyżowanie Minimalizujące Odległość (Distance Minimizing Crossover, DSX), Krzyżowanie Minimalizujące Równoodległość (Equidistance Minimizing Crossover, EMX), Krzyżowanie Zachowujące Odległość (Distance Preserving Crossover, DPX) i Krzyżowanie Bazujące na Podobieństwie (Similarity-Based Crossover, SBX). Operatory te mają na celu dostosowanie odległości między rozwiązaniami rodzicielskimi a potomnymi zgodnie z wybraną miarą niepodobieństwa. Skuteczność tych operatorów jest oceniana w odniesieniu do standardowych operatorów w serii eksperymentów obliczeniowych. Operator TSM osiąga w większości przypadków lepsze wyniki niż standardowy operator mutacji, podczas gdy proponowane operatory krzyżowania osiągają wyniki porównywalne do standardowych. W kolejnym wątku badawczym miary niepodobieństwa zastosowano w algorytmach sterowania różnorodnością, które są metodami mającymi na celu zwiększenie szerszego eksplorowania przestrzeni rozwiązań. Badanie porównuje standardowy algorytm ewolucyjny z niszowaniem (w wersji lokalnej i globalnej), poszukiwaniem nowości (novelty search, w wersji lokalnej i globalnej) i Algorytmem Genetycznym Sortowania Niezdominowanego II (Non-dominated Sorting Genetic Algorithm II, NSGA-II) wykorzystującymi różne miary niepodobieństwa. Analiza wyników pokazuje, w jaki sposób różne algorytmy i miary niepodobieństwa wpływają na wynik ewolucji pod względem jakości i heterogeniczności rozwiązań.

181

informatyka techniczna i telekomunikacja

Pobierz plik

publiczny

Aleksander Byrski

Kraków, Polska

05.02.2024

polski

Pobierz plik

publiczny

Andrzej Obuchowicz

Zielona Góra, Polska

14.02.2024

polski

Pobierz plik

publiczny

Michał Przewoźniczek

Wrocław, Polska

04.06.2024

polski

Pobierz plik

publiczny

rozprawa doktorska przed obroną

Poznań, Poland

02.08.2024