유전자 알고리즘은 염색체(프로세스 모델)집합을 랜덤으로 생성한 뒤 적합도를 평가하고,적합도를 기준으로 새로운 개체 집합을 생성하는 유전 연산을 여러 차례 반복 수행하여 적합도가 증가하는 방향으로 새로운 개체집합을 생성해 나갑니다.
유전자 프로세스 마이닝 알고리즘은 노이즈가 있는 데이터를 다룰 수 있다는 장점을 가지지만,
프로세스 모델을 도출하기 위한 연산 수행 시간이 길어 대용량 데이터인 경우가 많은 실제 프로세스를 분석하기에 어려움이 따릅니다.
이러한 한계를 개선하기 위해 하이브리드 유전자 알고리즘(hybrid genetic algorithm)이 제안되었고, 하이브리드 유전자 알고리즘의 대표적인 예시로는 시뮬레이티드 어닐링-유전자 프로세스 마이닝 알고리즘(SA-GPM)이 있습니다.
유전자 (프로세스 마이닝) 알고리즘
유전자 프로세스 마이닝 알고리즘(genetic process mining algorithm, GPM) : 이는 자연 생물 진화 과정의 원리로부터 착안한 메타 휴리스틱 알고리즘인 유전자 알고리즘을 이용한 프로세스 모델 도출 방법론
그림 1. 유전자 프로세스 마이닝 알고리즘 순서도
연산 수행 과정 : [그림 1]과 같은 과정을 거쳐 수행
하나의 프로세스 트리를 염색체(chromosome)로 정의
무작위로 염색체 집단(population)을 생성 (random population creation)
정의된 적합도 함수에 따라 각 염색체의 적합도를 측정(fitness measure) : 각 염색체(프로세스 트리)를 평가하는 적합도 함수로는 프로세스 모델의 순응도를 평가하는 4가지 척도(replay fitness, precision, simplicity, generalization)를 이용
replay fitness : 프로세스 모델이 이벤트 로그에 기록된 행동을 잘 재현할 수 있을지를 평가하기 위한 척도. 이는 이벤트 로그에 기록된 액티비티 수행 순서를 나타낸 문자열인 log trace와 프로세스 모델로 재현할 수 있는 액티비티의 수행 순서를 나타낸 문자열인 model trace의 공통부분을 비교함으로써 측정
precision : 프로세스 모델이 이벤트 로그에 기록되지 않은 예외 행동을 허용하고 있는지 평가하기 위한 척도. precision 또한 replay fitness와 마찬가지로 이벤트 로그로부터 추출한 log trace와 프로세스 모델로부터 생성된 model trace의 공통부분을 비교함으로써 측정
simplicity : 프로세스 모델의 단순도, 즉 프로세스 모델의 가독성을 평가하기 위한 기준. 단순성을 해치는 요소에 벌점을 부과하는 방법으로 측정.
generalization : 시스템에서 발생하는 예외적 행동 중 기록되지 않은 행동을 프로세스 모델이 얼마나 표현할 수 있을지에 대한 확장 가능성을 평가하기 위한 기준이 된다. 이는 프로세스 모델과 이벤트 로그를 비교해 모델과 이벤트 로그에서 공통적으로 나타나는 액티비티가 이벤트 로그에서 나타나는 빈도수를 이용해 계산
측정된 적합도를 기준으로 다음 세대에 전달할 개체를 선별하는 선택 연산(selection)과 염색체 집단의 원소들을 변형시키는 유전 연산(genetic operation)을 수행
새로운 자손을 생성하기 위해 무작위로 선택된 두 개체(부모)의 염색체 일부분을 교환하는 교차(crossover)
선택된 개체가 가진 염색체의 형질을 임의로 변화시킴으로써 새로운 자손을 생성하는 돌연변이(mutation)
유전자 프로세스 마이닝 알고리즘은 적합도 측정, 선택, 유전 연산의 과정을 반복해 적합도를 증가시키는 방향으로 새로운 염색체 집단을 생성
장점 : 노이즈가 있는 데이터를 다룰 수 있음
단점 : 근사 최적 프로세스 트리 도출을 위한 연산 시간이 길기 때문에 일반적으로 데이터의 크기가 큰 실제 데이터에 적용하기 어려움
유전 연산(genetic operation) 유전 연산은 유전자 알고리즘에서 중요한 개념이므로 도식을 통해 그 개념을 구체적으로 정리해 보았습니다.
다음 그림은 유전 연산을 수행할 때 한 세대 별로 fitness(적합도) 내림차순으로 정렬했을 때, 위로 갈수록 우수한 후보해(높은 적합도), 아래로 갈수록 낮은 적합도를 갖는 집합을 의미합니다. 1) 적합도가 높은 염색체 집합(elite set)는 다음 세대에 그대로 전달하는 elitism 연산 - 사회가 소수의 집단인 엘리트(elite)를 중심으로 움직인다고 보는 견해인 엘리트주의와 유사한 개념 2) 적합도가 낮은 집합(inferior set)은 삭제하고, 다시 랜덤 생성된 염색체로 대체하는 replace 연산 - 유전연산 중 elitism, replace
다음 그림은 elite set과 inferior set 어디에도 속하지 않는 중간 부분의 염색체 중
3) 사전에 정의된 비율(crossover rate, mutation rate)에 따라 선택된 염색체들에 crossover 및 mutation 연산을 수행해 변경된 집합(crossover set', mutation set')을 다음 세대로 넘겨주는 과정
4) 마지막으로 어떠한 연산도 적용되지 않은 집합(residual change operation set)은 그대로 다음 세대로 염색체 전달해줍니다.
유전연산 중 crossover, mutation
하이브리드 유전자 (프로세스 마이닝) 알고리즘
하이브리드 유전자 알고리즘 : GPM 알고리즘의 단점을 보완하기 위해 유전자 알고리즘에 다른 메타 휴리스틱 알고리즘을 접목한 방법론
하이브리드 유전자 알고리즘 기반의 프로세스 모델 도출 연구로는 유전자 알고리즘에 시뮬레이티드 어닐링 알고리즘을 결합해 [그림 2]와 같은 과정을 거쳐 프로세스 트리를 도출하는 알고리즘이 있음. (시뮬레이티드 어닐링에 대해서는 다른 글에서 살펴볼 예정입니다.)
그림 2. 시뮬레이티드 어닐링 - 유전자 프로세스 마이닝 알고리즘 순서도
이 알고리즘은 초기 프로세스 트리 집단 생성 연산과 선택 연산에서 적합도가 낮은 염색체들을 대체할 때 시뮬레이티드 어닐링을 이용해 프로세스 트리를 생성한다는 점에서 기존 유전자 알고리즘과 차이([그림 2] 하늘색 박스)
적합도 평가나 유전 연산 과정에서는 유전자 알고리즘과 동일한 방식의 연산을 수행
기존 연구(#6, Vahedian Khezerlou, A., Alizadeh, S.) 에서 시뮬레이티드 어닐링-유전자 프로세스 마이닝 알고리즘과 유전자 프로세스 마이닝 알고리즘을 비교하기 위해 같은 시간 동안 각 알고리즘을 통해 연산을 수행했을 때 시뮬레이티드 어닐링-유전자 프로세스 마이닝 알고리즘을 통해 도출된 프로세스 트리가 기존의 유전자 프로세스 마이닝 알고리즘을 통해 같은 시간 동안 연산을 거쳐 도출된 프로세스 트리보다 더 높은 평균적합도 값을 나타내었음
참고문헌
Buijs, J., Van Dongen, B., Van Der Aalst, W. M., “A genetic algorithm for discovering process trees”, IEEE Congress on Evolutionary Computation, pp. 10-15, 2012
Xue, Gang, Ye, Xiaohu, Yang, J., “Pseudo-parallel genetic algorithm in process mining”, IEEE Congress on Evolutionary Computation, pp. 623-626, 2012
A. K. Alves De Medeiros, a. J. M. M. W. “Genetic process mining”. Applications and Theory of Petri Nets, pp. 48–69, 2005
Van Eck, M. L., Buijs, J. C. A. M., & Van Dongen, B. F., “Genetic Process Mining: Alignment-Based Process Model Mutation”, Business Process Management Workshops, Lecture Notes in Business Information Processing, 202, pp. 291–303, 2015
Buijs, J., Van Dongen, B., Van Der Aalst, W. M., “On the Role of Fitness, Precision, Generalization and Simplicity in Process Discovery”, International Journal of Cooperative Information Systems, pp. 305–322, 2012
Vahedian Khezerlou, A., Alizadeh, S., “A new model for discovering process trees from event logs”, 41(3), Applied Intelligence, pp. 725–735.
Ou-Yang, C., Cheng, H. J., & Juan, Y. C., “An Integrated mining approach to discover business process models with parallel structures: towards fitness improvement”, 53(13), International Journal of Production Research, pp. 3888-3916, 2015
