인공생명 알고리즘의 고속화를 이용한 무요소법의 버블(bubble)생성 최적화 = Optimization of Bubble Generation in The Element Free Galerkin Method using Modified Artificial Life Algorithm

다국어 초록 (Multilingual Abstract)

Artificial life algorithm, one of the complexity theory, which is based on emergence of life creatures. But, It has a problem of the slow conversing speed in spite of it's merit, which is able to search solutions in multi-peak object functions.
In this study, it has been improved the conversing speed of the artificial life algorithm by introducing concepts from the relay-search micro genetic algorithm.
To verify it's efficiency in numerical problems, it was adapted in the bubble node generation method in Element Free Galerkin method (EFG), which is one of the optimized node generation methods was applied to reduce solution errors on the boundary area by the EFG. To improve it's efficiency of the solutions on boundary area, a new bubble generation method by using the high speed artificial life algorithm and the relay search micro genetic algorithm were adapted.
By using this new method, it is able to obtain more optimized results on boundary areas and to reduce it's errors instead of the 4th Runge-Kutta method. Therefore, it is expected that the proposed method ensures the comparatively improved numerical accuracy and stability on boundary areas.
As one of the complexity theories, the high speed artificial life algorithm is expected that it is useful to solve more general complex numerical problems.

국문 초록 (Abstract)

본 논문에서는 기존의 인공생명 알고리즘(artificial life algorithm)을 개선한 고속 인공생명 알고리즘(high speed artificial life algorithm)을 제안하였다. 기존의 알고리즘의 가상생태계가 인공생명체와 자원이 명확하게 구분이 된 평화로운 초원의 생태계를 모사하고 있는 것을 수정하여 보다 실제에 가까운 약육강식의 ‘정글의 법칙’을 도입하고 구조를 간략히 하기 위하여 기존 알고리즘에서 정의되었던 자원(resource)대신 순환구조에서 지정된 다른 종족의 생명체를 특정 생명체의 먹이가 되도록 하도록 하였다. 그리고 이탈리아의 경제학자 V. Pareto가 제안한 경제학이론의 하나인 ‘파레토 법칙(Pareto's law)'의 기본 개념을 도입하여 해의 정도를 높였다. 또한, 유전 알고리즘의 수렴 속도 향상을 위해 제안되었던 교대형 마이크로 유전 알고리즘(relay search genetic algorithm)의 개념들을 일부 도입하여 수렴속도를 크게 향상시켰다. 즉, 확률적 요소를 제거하고 패밀리를 도입하여 세대를 짧게 나누었다.
동일한 기법을 적용한 ‘교대형 마이크로 유전 알고리즘’이나 ‘고속 인공생명 알고리즘’의 속도가 빠르게 개선된 것은 공학적인 문제에 있어서 수시로 변화하는 ‘환경에 대한 적응’과 ‘생존’이라는 목적함수를 가진 실제 생명체의 경우와는 달리 정해진 공학적 문제를 해결하기 위하여 확정된 목적함수를 사용하기 때문이라고 생각된다. 따라서 불확실한 확률적 요소를 배제하여도 해의 결과에 크게 영향을 미치지 않는 것으로 생각되며 매 패밀리(family)마다 랜덤하게 위치를 이동하는 것으로 돌연변이와 같은 확률적 요소를 대신할 수 있다. 가상생태계를 보다 실제생태계에 가깝게 모델링함으로써 보다 정확한 해를 창발적으로 유도할 수 있었다.
무요소법의 버블(bubble)생성에 기존 ‘4차 Runge-Kutta법’을 대신해 고속 인공생명 알고리즘을 적용을 해 본 결과 기존의 수치해석 기법의 결과와 크게 다르지 않다는 것을 알 수 있었다. 해당 문제에 맞는 목적함수를 잘 구성하고 탐색구간을 적절히 지정할 경우, 교대형 마이크로 유전 알고리즘이나 고속 인공생명 알고리즘 모두 기존의 방법에 비해 크게 정도가 떨어지지 않는 결과를 나타내고 해를 찾는 수렴 속도 또한 상대적으로 크게 떨어지지 않음을 알 수 있었다. 특이할 만한 사실은 교대형 마이크로 알고리즘의 경우 단봉성 해만이 아니라 해가 2개의 쌍봉성 해도 찾을 수 있는 특징을 가지고 있다는 것이다. 그러나 3개 이상의 다봉성 해의 경우는 인공생명 알고리즘으로만 구할 수 있었다. 그리고 탐색영역의 크기가 유전 알고리즘과 인공생명 알고리즘의 계산시간에 절대적인 영향을 끼치는 것을 알 수 있었다. 특히 인공생명 알고리즘의 경우는 전체가 군집을 이루어 움직이기 때문에 보다 계산시간에 크게 좌우되는 것을 알 수 있었다.
생성된 버블을 이용하여 무요소해석의 해를 구한 결과는 예상대로 적분을 위한 가우스 점들을 균일한 형태로 규칙적으로 배열했을 경우보다 정도가 크게 떨어졌다. 특히, 경계부분의 가우스 점의 위치가 불규칙해질 경우 그 정도는 상당히 심하게 떨어졌다. 따라서 가능한 균일한 해를 얻기 위하여 그 경계부분에 있어서는 버블의 분포를 규칙으로 할 필요가 있다고 생각된다.
본 논문에서는 복잡성이론의 하나인 유전 알고리즘과 인공생명 알고리즘을 각각 개선한 수정된 알고리즘들을 제시하였으며 기존의 유전 알고리즘이나 인공생명 알고리즘이 공학적인 문제 해결에 주로 사용되었던 단순화된 최적화 문제보다는 좀 더 복잡한 수치해석 문제의 적용 및 비교를 통하여 복잡성이론이 보다 고차원적인 문제의 해결에도 적용가능한지 검토하고자 하였다.
고속 인공생명 알고리즘과 교대형 마이크로 유전 알고리즘 등 복잡성이론들을 이용할 경우에도 그 특성에 맞게 적절한 목적함수를 선정하고, 적당한 탐색구간을 지정한다면 기존의 복잡한 수치해석기법을 대신해서 상대적으로 간단하고 범용성을 가진 이론으로서 주어진 공학적 문제를 해결하는데 많은 도움이 될 수 있을 것이다. 또한, 기존의 알고리즘이 가진 단점을 보완한 고속 인공생명 알고리즘이나 교대형 마이크로 유전 알고리즘을 적절히 이용하면 조선분야를 포함한 다양한 분야의 각종 공학적인 최적화 문제들을 해결하는데 있어 널리 실용적으로 이용될 수 있을 것으로 생각된다.

목차 (Table of Contents)

• 제 1 장 서론 = 1
• 1.1 연구배경 = 1
• 1.2 연구동향 = 3
• 1.3 연구목적 및 내용 = 4
• 제 2 장 복잡계 이론(complex system theory) = 6
• 2.1 복잡계의 특징 = 6
• 2.1.1 창발(emergence) = 7
• 2.2 유전 알고리즘(Genetic Algorithm : GA) = 11
• 2.2.1 유전 알고리즘(GA) = 11
• 2.2.2 마이크로 유전 알고리즘(micro genetic algorithm) = 15
• 2.2.3 교대형 단순 유전 알고리즘(relay search simple genetic algorithm) = 17
• 2.2.4 교대형 마이크로 유전 알고리즘(relay search micro genetic algorithm) = 18
• 2.3 인공생명 알고리즘(Artificial Life Algorithm : ALA) = 19
• 2.3.1 인공생명(artificial life) = 19
• 2.3.2 인공생명 알고리즘(artificial life algorithm) = 21
• 2.4 고속 인공생명 알고리즘(high speed artificial life algorithm) = 26
• 2.4.1 고속 인공생명 알고리즘 = 26
• 제 3 장 무요소법(Element Free Galerkin Method) = 30
• 3.1 무요소법 정식화 = 30
• 3.1.1 변위함수의 근사화 = 30
• 3.1.2 이동최소제곱법(MLS)에 의한 형상함수의 결정 = 31
• 3.1.3 영향영역 = 41
• 3.1.4 가중함수(weight function) = 42
• 3.1.5 필수 경계조건을 만족시키기 위한 Lagrange 승수법 = 48
• 3.2 무요소법의 적응적 해석 = 55
• 3.2.1 오차 평가법 = 55
• 제 4 장 버블 생성(bubble generation) = 61
• 4.1. 버블 생성(bubble generation) = 61
• 4.2. 버블 생성방법 = 62
• 4.2.1 4차 Runge-Kutta법을 이용한 버블 생성 = 65
• 4.2.2 고속 인공생명 알고리즘을 이용한 버블 생성 = 67
• 제 5 장 수치해석 = 72
• 5.1 프로그램 = 72
• 5.1.1 최적화 계산 프로그램 = 72
• 5.1.2 버블 생성 프로그램 = 77
• 5.1.3 무요소 해석 프로그램 = 79
• 5.2 일반 함수 적용 예 = 82
• 5.2.1 Banana 함수 = 83
• 5.2.2 Camel 함수 = 84
• 5.2.3 다봉성 함수(multi-peak function) = 85
• 5.3 무요소 버블 생성 적용 예 = 86
• 5.3.1 외팔보 = 86
• 5.3.2 구멍이 있는 평판 = 87
• 제 6 장 검토 및 고찰 = 90
• 6.1 일반 함수 적용 예 = 90
• 6.1.1 Banana 함수 = 90
• 6.1.2 Camel 함수 = 93
• 6.1.3 Multi-peak 함수 = 96
• 6.2 무요소 버블 생성 적용 예 = 103
• 6.2.1 외팔보 = 104
• 6.2.2 구멍이 있는 평판 = 120
• 제 7 장 결론 = 124
• 참고문헌 = 126
• 감사의 글 = 132