Genetic Algorithm을 이용한 화학공정에서의 Multi-Modal 최적화

이원보, 박성준*, 윤인섭

서울대학교 화학공학과, LG-Caltex정유*

Multi-Modal Optimization on Chemical Process Using Genetic Algorithm

Won Bo Lee, Seong Jun Park* and En Sup Yoon

Dept. of Chem. Engineering, Seoul National Univ., LG-Caltex Oil Corp.*

1. 서론

GA(genetic algorithm)은 다양한 unimodal domain에서 유용함이 입증되었다. 그러나 여러개의 최적해를 확인하는 것이 필요한 문제들이 있다. 이런 최적화 전략이 필요한 부분의 대표적인 예는 공정합성이다. 전역해만을 구해서는 환경문제나, 공정의 안정성 문제등을 고려할 수가 없게 된다. 비록 전역해는 아니더라도 주변의 최적점들을 찾아서 위의 문제들을 고려함을로써 좀더 향상된 합성결과를 얻을 수 있을 것이다. 이렇게 전역해 및 주변의 최적점이 요구되는 문제에서는  여러 최적점에 효율적으로 수렴할 수 있는 알고리듬이 필요로 하게된다. 이런 목적으로 이용될 수 있는 알고리듬 중 하나가 MNC(Multi-Niche Crowding) method이다. 이 연구의 목적은 MNC방법을 이용하여 최적화를 수행할 수 있는 최적화 Tool(APROGAII)개발과 화학공정에의 적용이다.

2. 이론

2.1. 유전 알고리듬

2.1.1. GAs Benefits and Drawbacks

GA는 다음과 같은 장점을 지니고 있다. 첫째, 함수 값 자체만을 이용하고 여러 형태의 변수들을 동시에 처리해 줄 수 있으므로 문제의 형태에 관계없이 매우 다양한 문제에 적용시킬 수 있다. 둘째, 무작위로 발생된 초기 개체군을 이용하므로 해의 초기치에 비교적 민감하지 않다. 셋째, 초기치에 덜 민감한 결과로 생기는 결과로써 전역해에 도달할 가능성이 크다. 넷째, 개체군을 이용하기 때문에 여러 국지해에 동시에 수렴하는 것이 가능하다.

하지만, GA는 타 알고리듬에 비해 수렴 시간이 비교적 오래 걸리고, 적절한 완료 기준이 없으며, 사용되는 파라미터의 값들에 민감하다. 특히, 함수 최적화에 있어서 GA의 가장 큰 단점은 제약식을 다룰 수 있는 내재적인 방법이 없다는 것이다.

2.1.2. GAs Operators

Reproduction

GA는 개체들의 집합인 개체군으로 시작된다. 각 개체는 무작위로 발생된 인자를 지니고 있고, 각 개체는 그에 상응하는 적합도를 가진다. 이 적합도가 높으면 선택될 확률이 높아지고 그 개체가 여럿 복제된다. 선택될 확률이 낮으면 그 개체는 완전히 도태될 수도 있다. 이 과정을 통하여 좋은 인자를 가진 개체는 많이 선택되고 나쁜 인자를 가진 개체는 상대적으로 덜 선택되는 것이다.

Crossover

재생산만으로는 더 우수한 개체들을 생산해 낼 수는 없다. 이 작업을 해 주는 것이 교배 연산이다. 두 개의 어버이 열들이 선택되었을 때, 무작위로 교배점을 선택한 후, 교배점 오른쪽의 인자들을 서로 교환하는 것이 바로 교배이다.

Mutation

변종은 열 내의 하나의 인자에 대해서 행해지는 연산으로써, 구간 [0, 1]에서 발생한 난수가 변종 확률보다 낮을 때, 무작위로 선택된 인자가 새로운 인자로 바뀌게 된다. 변종은 최적화 과정에서 국지해에 수렴하는 것을 방지해 주는 중요한 연산이다.

2.1.3. Replacement Strategy

교체 방법은 크게 어버이 세대의 전체 개체를 자손으로 교체하는 Generational Model, 어버이 중 일부만을 자손으로 교체하는 Steady State Model과 연속적으로 세대를 교체하는 방법이 있다. 연속적으로 세대를 교체하는 방법은 MNC method에서도 사용된다. 또한 Multi-Objective Optimization에서도 사용할 수 있는 방법이다.

2.1.4. Constraint Handling Methods

유전 알고리듬은 그 특성상 제약식을 다룰 수 있는 내재적인 방법이 없다. 가장 일반적인 방법은 penalty 함수를 사용하는 것이다.

2.2. Multi-Modal Optimization Using GA

2.2.1. MNC method

그림2.1. Schematic Showing Crowding Factor Groups Created During the Replacement Step

MNC에서는 worst among the most similar라 불리우는 세대교체 방법을 수행한다. 이 과정의 목적은 하나의 개체를 자손으로 세대교체하기 위해 개체군으로부터 그 개체를 선택하는 것이다. 이 방법은 다음의 세 가지 과정으로 이루어진다. 첫번째로, 개체군으로부터 c개의 개체를 무작위로 선택하여 Cf개의 그룹을 만든다. 이러한 그룹들은 crowding factor groups이라고 불린다. 두 번째로, 각 그룹 내에서 자손과 가장 유사한 하나의 개체를 규명한다. 이 과정에 따라 세대교체를 위한 Cf개의 후보들이 주어진다. 자손과 가장 유사한 개체들로 이루어진 이 그룹에서 가장 낮은 적합성을 가지는 개체를 선택하여 자손과 교체한다.

이와 비슷한 방법으로 enhanced crowding(Goldberg, 1989)이 classifier systems에 사용되었지만, 여기서는 가장 적합성이 나쁜 후보들 중 가장 비슷한 개체가 선택되어 자손과 교체되는 방법이 쓰여졌다.

2.2.2. Algorithm

Generate Initial Population

Count Number

Select individual A for mating

Select group, Cs, randomly and Select M in Cs.

(M is the most similar)

Crossover

Mutation

Select groups, Cf, randomly and Select an individual among each Cf group

(Cf have s individuals and selected individual is the most similar with offspring)

Replace an individual among selected individuals with offspring

(an individual is worst among selected individuals)

Countnumber = Population Number?

Generation = Wanted Generation Number?

3. 결론

GA(Genetic Algorithm)를 이용한 MNC(Multi-Niche Crowding)method을 사용함으로써 여러 최적해에 동시 수렴이 가능하게 되었다. 이것은 이전의 Deterministic Optimization 뿐아니라 SGA(Simple Genetic Algorithm)로도  구현하기가 힘든 결과이다. 또한 이런 Niching법을 이용하여 Multi-Objective Optimization에도 응용하려고 한다.

감사

본 연구는 포항공과대학교 지능자동화연구센터를 통한 한국과학재단 우수센터 지원금에 의한 것입니다.

4. 참고문헌

[1] G. V. Reklaitis, A. Ravindran and K. M. Ragsdell, Engineering               Optimization : Methods and Applications, Wiley-Interscience, 1983

[2] T. F. Edgar and D. M. Himmelblau, Optimization of Chemical Processes,      McGRAW-HILL, 1989

[3] D. E. Goldberg, Genetic Algorithms : in Search, Optimization & Machine      Learning, Addison Wesley, 1989

[4] Practical Handbook of GENETIC ALGORITMS : Application Volume I,       edited by Lance Chambers, CRC Press, 1995

[5] Practical Handbook of GENETIC ALGORITMS : New Frontiers Volume      II, edited by Lance Chambers, CRC Press, 1995

[6] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution            Programs, 3rd ed., Springer, 1996

[7] Jeffrey Horn, Nicholas Nafpliotis, and David E. Goldberg, "A Niched          Pareto Genetic Algorithm for Multiobjective Optimization", Proceedings of      ICEC '94, pp. 82-87, 1994.