멀티 에이젼트시스템을 이용한 화학 공정에서의 자원 배분의 최적화

안성준, 어수영, 장태석, 윤인섭

서울대학교 응용화학부

Resource Allocation Optimization in Chemical Process with Multi-Agent System

Sungjoon Ahn, Sooyoung Eo, Tae Suk Chang, En Sup Yoon

Schoon of Chemical Engineering, Seoul National University

서론

자원 배분의 최적화 문제는 비단 화학공정에서 뿐만 아니라 많은 종류의 수학적 문제에서 마주치게되는 문제이다. 따라서 많은 연구자들은 자원 배분 문제를 해결하는 알고리듬을 연구했고, 많은 최적화 문제 풀이의 알고리듬은 자원 배분 문제를 해결하기 위한 것이다

그러나 대부분의 최적화 알고리듬은 화학공정과 같이 규모가 큰 문제에 적용하기에는 어려움이 있다. 화학공정은 그 특성상 수십만개 이상의 수지식을 가질뿐만 아니라 많은 식들이 심한 비선형성을 보이고, 많은 함수들은 함수의 형태를 해석적으로 얻기 곤란하기도 하며 설계변수들까지 고려하는 경우 MINLP와 같은 불연속 함수의 최적화 문제에 부딫히기도 한다. 따라서 많은 경우 계층적으로 분할하여 문제를 구성하여 풀게된다. 각각의 단계에서 서로다른 알고리듬을 이용해서 최적화를 하게된다.

멀티 에이젼트 시스템은 이러한 구조의 문제에 적합한 체계이다. 멀티에이젼트 시스템은 각각의 하위 구조에 에이젼트를 두고 에이젼트간의 협동을 통해서 문제를 해결하는 체계이다.이때 에이젼트의 역할은 각각의 하위구조의 성질에 대한 대리자의 역할을 맏는다. 따라서 각각의 에이젼트는 서로 에이젼트간의 통신을 통해서 최적화 문제를 해결해 나가게 된다. 이런 특성이 기존의 최적화 방법과는 다른 접근방법에서의 시도이고 또한 추세가 분산 작업이 점차 모든 분야에서 적용되기 때문에 그 활용범위가 크다.

에이젼트 시스템이 자원 배분문제의 적용에 이용되는 사례는 다양하다. J.M.Akkermans 등(1998)은 에너지 분배 문제에 에이젼트 시스템을 도입했고[4] B. A. Huberman 등(1995)은 건물의 온도제어를 위하여 각각의 사무실마다 필요한 냉방능력의 배분 문제를 에이젼트 시스템을 도입했다[2]. 이와 같이 적용되는 문제들에서 에이젼트를 활용하는 방법 또한 많은 제안이 있었다. 그 대표적인 것이 시장원리에 따른 자원 배분 방법이며 이를 기반으로 하여 많은 방법들이 제안되고 있다.

본연구에서는 에이젼트 시스템을 사용하여 자원 배분을 최적화하기위한 방법으로 시장원리를 응용한 방법을 따르되 자원기반의 배분 방법을 적용하고자 한다. 일반적으로 자원 배분 문제를 에이젼트 시스템을 이용하여 푸는 문제에서는 가격 기반의 방법이 주로 사용되었으나 가격 기반의 방법은 너무 많은 계산양을 갖는 단점이 있기 때문에 자원 기반의 방법을 적용하고자 한다[9]. 자원 기반의 방법은 Ygge(2000)등에 의하여 소개되었으며 그의 논문에서는 여러 가지 상품이 주어진 경우의 배분 문제를 푸는 예제를 시도하고 있다.

에이젼트 시스템

에이젼트의 개념은 연구들에 따라 그 정의가 다양하지만, 일반적으로 정의하자면 우리가 일상행활에서 사용하듯 균일하지 않은 서로 다른 일들을 수행해주는 객체라고 말할 수 있다[7]. 그만큼 에이젼트의 의미는 포괄적이지만, 이 논문에서 관심을 가지고자 하는 자원 배분의 문제에서 에이젼트의 정의는 자원을 필요로하는 단위와, 자원을 공급하는 단위 각각을 조업자를 대신해서 조정해 주는 역할을 맡는 소프트웨어와 하드웨어를 총칭하는 것이다. 앞서 언급되었듯이 멀티 에이젼트 시스템은 분산형 인공지능의 강점을 이어 받아 분산형 문제 해결에 효율적인 것으로 알려져 있다. 따라서 다수의 자원 공급원과 다수의 자원 수요가 존재하는 자원 배분 문제에서 효과적으로 사용될 수 있다.

화학공학 분야에서는 Lu 등(1996)과 Batres 등(1999)이 엔지니어링 설계와 운전 측면에서 에이젼트를 사용하여 동시공학(concurrent engineering)에 의한 공정의 설계와 응용에 에이젼트를 사용하고자 제안하였으며[4], 그 외에 Westerberg(1999)등은 공비(azeotrope) 혼합물의 물성치 계산을 위한 수치 해석에 에이젼트를 응용하여 공정 설계에 응용하였다[1]. 한편, Ygge(1999)는 자원 배분(resource allocation)문제에 에이젼트를 도입한 국지 제어(local control)가 통합된 제어(Global control) 시스템에 못지 않은 성능을 보일수 있다는 점을 보여 최적화 문제에 응용하였다[4].

에이젼트는 용도에 따라 여러 가지 차원에서 분류될 수 있다.

첫째, 에이젼트는 유동성(mobility)에 따라 분류될 수 있다. 이에 따른다면 정적 에이젼트(static agent)와 동적 에이젼트(mobile agent)가 있을 수 있다.

둘째, 에이젼트가 스스로의 사고체계를 가지고 있는가 아니면 자극에 대하여 반응적으로 작동하는가에 따라 생각하는 에이젼트(deliberative agent)와 반응적 에이젼트(reactive agent)로 분류할 수 있다. 생각하는 에이젼트는 사고 체계를 가지고 있으며 내부적인 추론 모델을 가지고 있는 반면, 반응적 에이젼트는 자체적으로 추론할 수 없으며 단지 주어진 공정의 환경으로 부터의 자극에 정해진 법칙에 따라 정확히 응답으르 보이는 에이젼트이다.

셋째, 에이젼트가 갖는 최소한의 공통적인 속성[그림]인 자치(autonomy), 협동(cooperatioin), 학습(learn)에 의한 분류이다. 자치, 협동, 학습은 에이젼트에 관해 연구한 많은 연구자들이 공통적으로 꼽는 속성이며 따라서 이 세가지 속성이 곧 에이젼트의 특징을 매우 잘 표현해 주고 있다. 자치란 사람의 도움 없이 에이젼트가 작용할 수 있는 능력을 말하며, 협동이란 에이젼트가 사회성을 가짐으로써 다른 에이젼트와 협동할 수 있는 능력을 말하고, 학습은 에이젼트가 상호 작용을 하는 동안 외부 환경으로부터 학습할 수 있는 능력을 말한다. 이러한 에이젼트의 세가지 속성에 따라 네가지의 분류가 가능한데 이들은 협동적 에이젼트(collaborative agents), 협동적 학습형 에이젼트(collaborative learning agents), 인터페이스 에이젼트(interface agents), 그리고 스마트 에이젼트(smart agents)로 분류할 수 있다(Bradshaw, 1997)[7].

그림  에이젼트의 속성에 의한 분류

넷째, 혼성 에이젼트로서 두가지 이상의 에이젼트의 개념을 하나의 에이젼트에 합친 형태이다. 에이젼트는정형적인 개념이 아니고 필요에 따라 여러 개념을 혼합하여 사용하는 예는 어디에서든 볼 수 있다.

이와 같이 에이젼트는 여러 관점에서 분류될 수가 있지만 지금까지 나열한 분류 기준들을 개별적으로 적용할 수 있는 것이 아니며 실제로 에이젼ㅌ의 분류는 매우 다차원 적이므로 우리가 실제적으로 이른바 실용적으로 사용할 수 있는 에이젼트 들만을 나누어 본다면 다음과 같은 일곱가지 유형의 에이젼트들을 뽑을 수 있다. (Chang, []

(1) 협동적 에이젼트 (Collaborative agents)

(2) 인터페이스 에이젼트 (Interface agents)

(3) 이동 에이젼트 (Mobile agents)

(4) 정보 에이젼트 (Information agents)

(5) 반응적 에이젼트 (Reactive agents)

(6) 혼성 에이젼트 (Hybrid agents)

(7) 스마트 에이젼트 (Smart agents)

이상의 범주 중 두 가지 이상의 범주를 연합하여 사용하는 시스템을 이질적 에이젼트 시스템(Heterogeneous agent systems)이라고 한다.

이와 같은 에이젼트의 분류중에서 본 연구에서 사용하고자 하는 에이젼트는 협동적 에이젼트이다. 자원 배분의 문제는 문제가 본질적으로 분산되어 있는 구조의 문제를 해결하는 것이다. 따라서 협동적인 에이젼트 시스템의 효과가 진가를 발휘할 수 있는 문제이다. 자원배분의 문제에서 각각의 에이젼트는 각각의 공급원과 수요자의 상태를 관리하고 조정한다. 한편으로 다른 에이젼트와의 통신을 통해 최적의 자원 배분을 찾아낸다. 여기서 중요한 것은 에이젼트간의 협의를 통해 최적의 배분을 찾아내는 알고리듬이며 이에 대하여 다음에 다룬다.

시장원리 기반 계획법

시장원리 기반 계획법은 협동적 에이젼트 시스템에서 에이젼트간의 상호 협력의 방법으로서 제안된 방법이다. Surtherland(1968)은 컴퓨터의 계산능력을 배분하는 문제에 시장원리를 도입하는 방법을 제안하였으며[5], 1989년에는 Kurose 와 Simha에 의하여 파일 배정문제에 시장 평형원리를 도입하여 최적해를 구할 수 있다는 것을 보였고[6], 비슷한 배정문제에 대하여 1992년 Bertsekas도 해를 구할 수 있다는 것을 보였다[3]. Bikhchandani와 Mamer는 1997년에 유사 선형함수 형태의 효용함수를 갖는 경우 시장평형원리에 기반한 방법이 Pareto 최적해를 구할수 있다는 것을 보였다[8].

이러한 시장원리 기반 계획법은 가격을 매계변수로 하여 이루어진다. 일반적으로 각각의 에이젼트는 필요한 자원에 대한 수요에 의하여 나름대로의 가격과 수요를 경매자에게 제안한다. 경매자는 각각의 에이젼트로부터 받은 가격과 수요를 통해 최적의 가격을 제안한 쪽에 자원을 우선적으로 할당하며, 이 때 자원을 할당 받지 못한 에이젼트들을 다시 새로운 가격을 가지고 경매에 참여하게 된다.

본 연구에서는 이와 같은 시장원리 기반 계획법에 수정을 가했다. 에이젼트를 사용하는 경우 에이젼트의 중요한 특성 중 하나인 학습의 능력을 이용하고자 하는 점이다. 경매가 매번 자원 할당이 이루어 질 때마다 이루어 진다면 각각의 에이젼트들은 경험적으로 자신에게 적합한 가격 - 수요 곡선을 학습하게 된다. 따라서 이를 이용하면 에이젼트들은 어느 정도 시간 이후에는 굳이 경매에 의존하지 않고도 자신에게 필요한 만큼의 자원을 가져올 수 있다. 이때는 경매자는 단지 에이젼트들이 보낸 정보를 감시하는 역할만으로 충분하게 된다.

사례연구

본 연구에서는 Hubermans와 S. Clearwater에 의하여 수행되었던 냉각 용량의 배분 문제[2]를 수행하고자 한다. 냉각용량의 배분 문제는 많은 시도 사례가 있었으나 에이젼트의 특성을 완전히 활용하지 못한 점이 있었다. 따라서 본 연구에서는 에이젼트의 학습적 측면을 활용하여 보다 향상된 결과를 볼 수 있다고 생각하여 수행하였다.

문제는 동서남북 4개의 방향으로 있는 100개의 사무실에 한정된 냉각용량을 할당하는 것이다. 에이젼트는 각각의 사무실 마다 있어서 각각 사무실에서 필요한 용량과 가격을 경매자에게 제안한다. 경매자는 자원을 적절하게 할당하게 되며 에이젼트는 학습을 통해 점차적으로 자신에게 적합한 용량을 경매를 거치지 않고 할당받게 된다.

수행 결과 학습없이 경매를 통하는 경우와 비교하여 같은 정도의 표준편차 범위안에서 냉각용량 할당을 달성했으며, 학습을 통해 하는 경우 경매의 과정을 제거하고 수행하여도 같은 결과를 얻을 수 있었다.

경매의 과정을 생략할 수 있는 경우의 장점은 몇몇 에이젼트들에 이상이 발생하는 경우에도 문제없이 나머지 에이젼트들이 작동할 수 있다는 점이다. 이에 대하여는 추후 보다 연구해 나갈 예정이다.

참고문헌

[1] 장태석, □멀티 에이젼트와 기능-거동 모델링에 기반한 화학공정의 이상진단 시스템□, 박사학위 논문, 서울대학교 화학공학과 (2000)

[2] B. A. Hubermans, S. Clearwater, "A multi-agent system for controlling building enviroments" In Lesser, V(Ed.) Proceedings of the First International Conference on Multi-Agent Systems, ICMAS'95, pp 171-176. AAAI Press /The MIT Press, Menlo Park, CA. (1996)

[3] D. Bertsekas, "Auction algorithms for network flow problems: A tutorial introduction." Computational Optimization and Applications, pp 7-66 (1992)

[4] F. Ygge, J. M. Akkermans, "Decentralized Market versus Cntral Control: A Comparative Study", Journal of Artificial Intelligence Reasearch 11, pp 301-333 (1999)

[5] I. E. Sutherland, "A futures market in computer time." Communications of the ACM 11(6), pp 449-451 (1968)

[6] J. F. Kurose, & R. Simha, "A microeconomic approach to optimal resource allocation in distributed omputer systems." IEEE Transactions on Computers, 38(5), pp 705-717. (1989)

[7] J. M. Bradshaw (Ed.). "Software Agents" AAAI Press/The MIT Press, Menl Park, CA (1997)

[8] S. Bikhchandani & J. W. Mamer "Competitive equilibrium in an exchange economy with indivisibilities" Journal of Ecomomic Theory, 74 385-413 (1997)

[9] F. Ygge, J. M. Akkermans, "Resource-Oriented Multicommodity Market Algorithms" Autonomous Agents and Multi-Agent Systems, 3, pp 53-71 (2000)