개선된 대규모 단계 마르코프 체인이 포함된 유전 알고리듬을 이용한

화학 공정 산업에서의 다목적 함수 최적화

이상화, 신동일, 윤인섭

서울대학교 응용화학부

Multiobjective Optimization Using A Genetic Algorithm With An Improved

Large-Step Markov Chain In The Chemical Process Industry

Sanghwa Lee, Dongil Shin, Ensup Yoon

School of Chemical Engineering, Seoul National University

서론

화학공학 분야에서 다목적 함수의 최적화는 1980년대 초에 Sophos 등[1]에 의해 활발히 이루어졌고, 근래에는 Papalexandri 등[2], Lim 등[3]에 의해 연구되고 있다. 하지만, 다목적 함수는 여러 목적 함수를 동시에 만족시켜야 한다는 어려움이 존재하므로, 여러 가지 수정된 알고리듬 및 새로운 알고리듬을 이용하여 풀고자 하는 노력이 있었는데, 그 중 하나가 유전 알고리듬(Genetic Algorithm)을 이용한 방법이다. 유전 알고리듬을 이용한 문제 해결 노력은 Schaffer[4]에 의해 처음 시도되어, Fonseca 등[5], Horn 등[6], 그리고 이 등[7], 류 등[8]에 의해 연구되고 있다. 본 연구에서는 화학 공정에 있어서 다목적 함수 최적화를 위한 도구로서 개선된 유전 알고리듬을 제시하였다. 제안된 유전 알고리듬에는 대규모 단계 마르코프 체인(Large-Step Markov Chain)을 포함하고 있어, 유전 알고리듬의 단점인 수렴 시간을 대폭적으로 줄여준다. 또한, 해들의 fine tuning을 가능하게 하여, 완만한 Pareto Otimal Set을 도출할 수 있었다.

이론

1. Genetic Algorithm(GA)

유전 알고리듬은 encoding영역과 decoding영역을 넘나들면서, 적합도에 따라 우수한 성능을 가지는 해집합은 증가되고, 그렇지 못한 해집합은 점차 소멸되는 자연 법칙을 이용한 알고리듬이다. 유전 알고리듬은 목적 함수 자체의 정보만 필요로 하므로 추가적인 정보가 필요 없으며, 해가 개체군으로 얻어진다는 장점을 가진 확률론적인 방법이다. 본 연구의 최적화 수행을 위해 구현된 유전 알고리듬에서 사용되는 연산자는 각각 다음과 같은 것들을 사용하였다.

encoding과 selection 연산자로는 이진 coding과 Roulette-Wheel selection을 선택하였으며, replacement 방법은 부분적인 generational replacement 방법을 사용하였다. 즉, 부분적인 해집합을 추출하여 적합도에 따른 연산을 수행한 뒤, 그것을 부모 개체군과 교체하는 방식을 택했다. 또한, crossover 연산자로는 함께 구현된 Large-Step Markov Cahin이 지역 최적점에 빨리 수렴한다는 성질이 있으므로,  population diversity와 selective pressure 사이의 적절한 균형을 유지하기 위해 multipoint crossover를 채택하였다.

(1) Pareto Optimality

다목적 함수의 처리 및 적합도 평가를 위해서 Pareto Optimality 개념을 도입하여 순위매김(ranking)을 실시하였다. 즉, 하나의 목적함수에 대하여 ranking을 실시하여 1이 되는 개체군들만 추출하고, 다시 다른 목적함수에 대한 ranking을 실시하였다. 모두 1이 되는 개체군들만 모아서 최종적으로 rank 1을 부여하고, 나머지 개체군들에 대해 다시 ranking을 실시하여 rank 2, 3 등을 부여, 정량화 시켰다.

(2) Penalty Function

유전 알고리듬은 기본적으로 목적 함수만의 정보를 이용함으로써, 제약조건을 처리하기가 힘들다는 단점이 있다. 이 부분을 처리하기 위해, 목적함수의 적합도 계산에 있어서 penalty 항을 첨가시켜 제약조건을 적절히 고려하도록 하였다. 사용된 penalty function은 다음과 같다.

[eqn: rm &P(tilde x , N_{i t e r}) ~= ~ f_avg · e^N_{i t e r} ·[ SUM from { {i}=1} to m PHI_1 (tilde x) + SUM from { {i}=m+1} to n PHI_2 (tilde x) ] #& rm PHI_1 (tilde x ) ~= ~ 0 ~ if ~ | h_i | _max ~ = ~ 0 ~ ,otherwise ~ { | h_i ( tilde x )| }over {| h_i | _max} #& rm PHI_2 ( tilde x ) ~= ~ 0 ~ if ~ | g_i | _max ~ = ~ 0 ~ ,otherwise ~ { | min ( g_i ( tilde x ) , 0 )| }over {| g_i | _max}]

여기서, [eqn: rm f_avg]는 평균 적합도, N은 세대수, h는 등호, g는 부등호 제약조건이다.

2. Large-Step Markov Chain(LSMC)

(1) Improved Large-Step Markov Chain

large-step Markov chain은 초기해가 주어지면 해의 섭동(perturbation)과 지역 최적화(local optimization)의 과정을 되풀이하면서 최적점을 찾아가는 알고리듬이다.  이 알고리듬에서는 지역 최적화로 구한 해와 섭동 이전의 해를 비교하여 우수한 해를 채택하는 루프(loop)가 존재하는데, 지역 최적화로 구해진 해가 이전의 해에 비하여 열등하더라도 어떤 확률을 가지고 그 해를 채택할 수 있는 반 움직임(negative move) 과정을 포함하고 있다. 이는 simulated annealing에서 사용되는 기법과 유사한 방법으로, 반 움직임 과정이 없다면 미분 방법과 비슷한 효과를 낸다. 원래 large-step Markov chain은 하나의 해로 최적점을 구하기 위하여 사용되는 알고리듬으로, 여러 개의 해를 다루기 위해서는 약간의 보정이 필요하다. Fukuga 등[9] 등이 여러 개의 해를 다루는 방법으로 섭동 시에 여러 개의 출발점을 두는 방법 등을 제시하였다. 본 연구에서의 large-step Markove chain은 유전 알고리듬에 이어서 미세 조율과 수렴 시간 감소를 위한 방안으로 사용되었고, 복수개의 해를 다루면서 전체 탐색 구간의 일정 비율에 해당되는 섭동을 주도록 알고리듬을 구성하였다. 또한, 다목적 함수를 다루어야 하므로 각각의 함수에 대한 지역 최적화는 다목적 함수 최적화의 알고리듬에 부적절하여 삭제하고, 함수값을 비교·이동함으로써 지역 최적화에 도달하도록 하였다. 최적점으로의 이동과 반 움직임을 위한 알고리듬에 사용되는 함수값 비교로는 Pareto ranking을 사용하였다. 따라서, 여러 개의 목적 함수값을 비교하여 얻은 단일 비교 기준인 Pareto ranking을 통하여 최적점에 도달하는 알고리듬을 구성하였다. 구현된 알고리듬의 다른 특징으로는 섭동 이전의 해집합과 섭동 이후의 해집합을 함께 고려함으로써, rank가 1인 해들의 계수가 빠른 속도로 증가한다는 점이다. 제시한 다목적 함수를 위한 변형된 large-step Markov chain 알고리듬은 <그림 1>과 같다.

<그림 > Improved large-step Markov chain

<그림 > Implemented algorithm

3. Proposed Algorithm

유전 알고리듬과 수정된 large-step Markov chain을 이용하여, 제안된 최적화 도구는 <그림 2>와 같다.

사례연구

다음은 Bihn[10]과 류 등[8]에 의해 다목적 함수 최적화의 test 예제로 사용된 함수이다. test는 MATLAB에 의해 짜여진 코드로서, Genuine Pentium CPU 350Mhz에서 행해졌다. 사용된 파라미터들은 <표 1>과 같으며, 대략 20sec 정도의 비슷한 시간에 의해 얻어진 Pareto optimal set의 그래프는 <그림 3>, <그림 4>와 같다. 유전 알고리듬만 사용했을 경우 보다 섬세한 조율(fine tuning)과 내삽이 가능함을 알 수 있다. 또한, <표 2>의 파라미터로 <그림 5>와 <그림 6>의 비슷한 정도의 해집합을 얻는 데 있어서, 구현된 알고리듬이 180배 정도 수렴 시간을 단축시킬

<그림 4> GA-LSMC

<그림 3> GA

<표 1> 사용된 파라미터

<그림 6> GA-LSMC:5.8280sec

<그림 5> GA:14min 0.308sec

수 있음을 알 수 있다.

결과 및 토론

본 연구에서는 유전 알고리듬의 단점으로 지적되는 fine tuning과 수렴 시간의 보완을 위해 개선된 large-step Markov chain을 사용함으로써, 유전 알고리듬의 단점을 보완하려고 하였다. test 문제를 통해서, 제안된 알고리듬은 유전 알고리듬의 장점은 살리고, 단점은 개선시킴으로써 그 효과를 확인할 수 있었다. 하지만, 많은 파라미터들을 조작 변수로 둠으로써 적절한 값의 선택을 위한 노력이 필요하다.

감사의 글

본 연구는 교육부의 두뇌한국 21사업의 지원에 의해 이루어졌으므로, 이에 감사의 글을 올립니다.

참고문헌

1) Sophos, A., Rotstein, E. and Stephanopoulos, G., □Multiobjective Analysis in Modeling the Petrochemical Industry□, Chemical Engineering Science, 35, pp.2415-2426(1980)

2) Papalexandri, Katerina P. and Dimkou, Theodora I., □A Parametric Mixed-Integer Optimization Algorithm for Multiobjective Engineering Problems Involving Discrete Decisions□, Ind. Eng. Chem. Res., 37, pp.1866-1882(1998)

3) Lim, Young Il, Floquet, Pascal and Joulia, Xavier, □Multiobjective Optimization in Terms of Economics and Potential Environment Impact for Process Design and Analysis in a Chemical Process Simulator□, Ind. Eng. Chem. Res., 38, pp.4729-4741(1999)

4) Schaffer, J. D., PhD Dissertation, Vanderbilt University, Nashville(1984)

5) Fonseca, C. M. and Fleming, P. J., □An Overview of Evolutionary Algorithms in Multiobjective Optimization□, Evolutionary Computation, 3(1), pp.1-16(1995)

6) Horn, J. and Nafpliotis, N., □Multiobjective Optimization Using the Niched Pareto Genetic Algorithm□, Department of Computer Science, University of Illinois at Urbana-Champaign, IlliGAL Report 93005(1995)

7) 이원보, 박성준, 윤인섭, □Genetic Algorithm을 이용한 화학공정에서의 Multi-Modal 및 Multi-Objective 최적화□, Proceedings of '97 KIGAS Autumn Conference, pp.115-120(1997)

8) 류현욱, 신동일, 윤인섭, □A Multiobjective Optimization Method based on Genetic Algorithms□, Proceedings of '99 KIGAS Autumn Conference, pp.2597-2600(1999)

9) Fukunaga, Alex S., Huang, Dennis J. -H. and Kahng, Andrew B., □Large-Step Markov Chain Variants for VLSI Netlist Partitioning□, Proceedings of the IEEE International Symposium on Circuits and Systems - Volume 4, pp.496-499(1996)

10) Bihn, To Thanh and Ulrich Korn., □MOBES: A Multiobjective Evolution Strategy for Constrained Optimization Problems□, Proceedings of the 3rd Int. Conf. on Genetic Algorithms(1997)