This site uses cookies.
Some of these cookies are essential to the operation of the site,
while others help to improve your experience by providing insights into how the site is being used.
For more information, please see the ProZ.com privacy policy.
This person has a SecurePRO™ card. Because this person is not a ProZ.com Plus subscriber, to view his or her SecurePRO™ card you must be a ProZ.com Business member or Plus subscriber.
Affiliations
This person is not affiliated with any business or Blue Board record at ProZ.com.
Korean to English: Improved WTA problem solving method using a parallel genetic algorithm which applied the RMI initialization method
Source text - Korean rmi 초기화 방법을 적용한 병렬 유전자 알고리즘을 이용하여 개선된 WTA 문제 해결 방법
1. 서론
무기 할당(WTA : Weapon Target Allocation)문제는 아군에게 침투하는 적의 타겟들로부터 아군자산의 피해를 최소화하거나 각 타겟에 대한 격추확률을 최대화할 수 있도록 아군의 방어무기체계를 각 타겟에 적절히 할당하는 방법을 찾는 문제이다. WTA문제는 전형적인 NP-Complete문제로 다양한 Optimization 알고리즘들을 이용하여 WTA 문제를 해결하는 연구가 진행되고 있다. 휴리스틱 알고리즘은 임의로 한해를 선택하여 그 해를 조금씩 개선시켜 나가 근사해를 찾아가는 방법들로 WTA 문제를 해결하는데 사용된다. 대표적으로 ACO(Ant Colony Optimization)[10], Simulated annealing[14], TABU search[12, 13], PSO(Particle Swarm Optimization)[11], 유전자 알고리즘(GA : Genetic Algorithm) 등이 대표적인 휴리스틱 알고리즘들이다.
유전자 알고리즘은 이산과 연속 변수들의 문제를 메타 휴리스틱 방법으로 해결하는 알고리즘이다. 여러 개의 Individual로 이루어진 Population을 형성하여, 교차 및 변이 등의 유전자 연산(Genetic Operator)을 통해 최적해 또는 ‘최적에 가까운’ 근사해로 찾아갈 수 있도록 여러 세대를 거치면서 값을 진화시키는 알고리즘이다[6].
WTA 문제는 전장상황에서 일어나는 문제인데, 전장상황의 특징은 계속적으로 변경되는 타겟과 타겟에 따른 위협 순위, 그리고 실시간 대응과 그에 따른 짧은 제한 시간이다. 이러한 제한적인 전장상황에는 짧은 시간 안에 질 좋은 전역 최적해를 찾는 것이 가장 중요하다. 따라서 본 논문에서는 우리가 제안하는 RMI Population 초기화 방법을 적용한 새로운 병렬 유전자 알고리즘을 제안하고자 한다. 제안하는 알고리즘은 개선된 초기화 방법과 WTA 문제에 적합한 효율적인 병렬 유전자 알고리즘을 이용하여 두 단계에 걸쳐서 GA의 수렴속도를 개선한다. 또한 두 단계의 방법에 의해 넓은 영역의 문제공간을 빠르게 탐색할 수 있기 때문에 질 좋은 전역 해를 얻을 수 있다. 제안하는 알고리즘은 기존의 WTA 문제 해결 알고리즘보다 속도가 빠르고, 높은 Quality의 전역 최적해를 얻을 수 있기 때문에 적의 위협에 대해 실시간으로 대응할 수 있는 WTA 시스템을 구축할 수 있다.
2. 관련연구
2.1 WTA 문제
WTA문제는 Weapon Allocation, Weapon Assignment라고도 불리우며, ‘확인된 위협에 대해 무기 시스템이 반응하여 무기를 할당하는 것[2]’으로 일반적으로 타겟에 대해 공격 가능한 무기를 배치시킴으로써 타겟에 대한 위협수치를 최소화 할 수 있는 최적화된 무기할당을 찾는 것이다. WTA 문제는 간단하게 아래 식 (1)의 함수 값을 최소화하는 것으로 명시할 수 있다[5].
(1)
제한 사항으로는 아래 식 (2)가 있다.
(2)
여기서 변수 는 아래 식 (3)에 따라 이진수 변수로 정의된다.
(3)
식(1)에서 변수 는 아군의 무기 집합( )이고, 는 접근하는 타겟의 집합이다. 는 타겟 i 에 대해 무기 k가 격추시킬 수 있는 확률이며, 는 타겟 i 에 대한 위협수치이다. 또한 모든 아군의 무기 에 대해 1개의 타겟들이 무조건 할당되어야 한다. 이렇게 정의된 WTA 문제를 The Static Target-Based Weapon Allocation라고 한다.
여기서 솔루션 는 아래와 같이 표현하며, 각 행렬의 값은 0 아니면 1로 1이면 해당 행의 무기에 해당 열의 타겟이 할당되었다는 것이다.
2.2 GA 초기화 문제
GA Population 초기화는 최초 염색체 Population을 만들어내는 과정으로 대부분 임의 난수 생성기를 이용하여 임의의 수로 생성하는 경우가 대부분이다. 하지만 이러한 Population 초기화 과정은 유전자 알고리즘이 탐색할 문제의 공간을 형성하는 과정으로 공간에 각 염색체를 어떻게 배치하느냐에 따라 유전자 알고리즘의 성능과 효율성에 영향을 줄 수 있다[3].
초기화 문제는 크게 두 가지 고려할 사항이 있는데, 얼마나 문제공간에 탐색공간을 분산시킬 것인가와 빠르게 좋은 해를 찾을 수 있도록 유도할 것인가의 문제를 다루게 된다. 이 두 부분은 서로 상반되는 속성을 가지고 있다.
탐색공간의 분산 문제는 얼마나 문제 공간 내에 효율적이고 광범위하게 탐색 공간(염색체)를 분산시킬 것인가에 대한 문제이다. 만약 Global Optimization 문제에서 탐색공간의 형성이 잘못되어 Global optimum을 탐색하지 못하여 더 좋은 해를 찾지 못하고(유전 연산자의 잘못된 설계나 유전자 파라미터에 잘못된 설정, 잘못된 염색체 표현방법들도 영향을 줄 수 있다), Local Optimum으로 잘 못 수렴하는 경우가 발생할 수 있다. 이렇게 되면 원하지 않게 가장 좋은 근사해가 아닌 잘못 수렴한 해를 얻을 수 있다.
좋은 해를 빠르게 찾을 수 있도록 유도하는 문제는 최초 Population 초기화를 수행할 때 전혀 의미 없는 임의의 수가 아닌 도메인의 Knowledge를 적용하거나 Local Search 등의 빠른 탐색 알고리즘을 적용하여 최초 탐색공간을 근사 해의 주변으로 위치하여 그 안에서 좀 더 빠르게 근사해를 찾도록 유도하는 것이다. 유전자 알고리즘의 개념적인 원리로 봤을 때 최초 염색체 Population을 형성할 때 유전형질이 좋은(우성 유전자) 염색체 내에 적용하여 우성형질을 이용하여 좋은 해를 빠르게 찾도록 하는 것이라고 볼 수 있다.
이러한 두 가지 고려사항은 각 도메인의 특성이나 제약사항, 제한사항 등에 따라 적절하게 고려되어 유전자 알고리즘을 사용해야한다. 본 논문에서 다루는 무기할당 문제의 경우 적의 침투가 발생하였을 시 최대한 빠르게 무기를 할당해야 하며, 일정 제한시간 내에 꼭 무기를 할당해야한다. 따라서 초기 Population 생성시 도메인의 Knowledge나 Local Search방법 등을 이용하여 초기 Population에 우성 유전자를 배포시켜, 빠르게 근사해로 유도될 수 있도록 하는 것이 유리할 것으로 판단된다.
2.3 병렬유전자 알고리즘
유전자 알고리즘은 선택, 교차, 변이로 이루어진 유전자 오퍼레이터를 반복적으로 수행하면서 최적의 해를 얻는 알고리즘이다. 수행시간이 지날수록 점차 하나의 최적해로 수렴하는 형태가 나타난다. 이러한 유전자 알고리즘은 여러 세대를 거쳐 많은 수의 반복수행을 해야하기 때문에 계산량이 많고, 시간이 오래 걸린다는 단점이 있다. 이러한 문제점을 해결하기 위해 여러 개의 부분 집단(Sub-population)을 활용하여 동시에 유전자 오퍼레이터를 수행하는 병렬 유전 알고리즘이 연구되었다[ADA 94, GOR 93, LIN 94].
병렬 유전자 알고리즘에는 크게 세 가지 형태로 분류할 수 있다 : (1) global single-population master-slave GAs, (2) single-population fine-grained, and (3) multiple-population coarse-grained GAs.
master-slave GA 방법은 Master에서 유전자 오퍼레이터를 수행하고, slave들에서는 individual들을 분산시켜 단순히 fitness 값만 계산하는 역할을 한다. fine-grained GA 방법은 대규모 병렬 컴퓨터에 적합한 방법으로 공간-구조 집단을 구성한다. 선택과 교차는 근처의 이웃 집단들과 수행하도록 제한하지만, 이웃끼리 모든 individual에 대해 상호작용을 할 수 있도록 허용한다.
Coarse-grained 병렬처리방법은 집단을 몇 가지의 부 개체군(sub populatoin)으로 나누어서 이 몇 개의 개체군내에서만 서로 독립적으로 유전 연산자가 적용되기 때문에 각 부개체집단은 순차적 진화연산과 동일하게 된다. 순차적 진화연산과 차이를 보이는 부분은 개체의 교환이다. 이것을 이주라고 부른다. Coarse-grained 알고리즘을 구성하는 파라미터는 기존의 재조합, 돌연변이연산, 선택 과 이주이다. Prettey[12]는 이 방법에서 부 개체집단간에 독립적으로 일어나는 재조합, 돌연변이연산, 선택은 결과적으로는 순차적 진화연산과 같은 효과를 나타내고, 이주에 의해서 새로운 개체를 소개하고 빠른 수렴효과를 보인다고 밝혔다. 이주는 이주율(migration rate)과 이주간격(migration interval)로 나뉜다. 이주율은 이주시키는 개체의 양을 뜻하는 것이고, 이주간격은 얼마나 자주 개체를 이주시킬 것인가를 의미한다. 본 논문에서는 rmi 초기화 방법을 적용한 개선된 multiple-population GA 방법을 제안하였다.
3. rmi초기화 방법을 적용한 병렬 유전자 알고리즘
3.1 rmi 초기화 방법
본 논문에서 연구 중인 유전자 알고리즘 Population 초기화 방법은 효율적으로 Population을 초기화하여 WTA 문제를 해결함에 있어서 유전자 알고리즘의 성능을 개선하고자 한다. 제안하고자 하는 초기화 알고리즘은 다음과 같다. 알고리즘에서 사용되는 파라미터는 아래와 같다.
∙ popSize = population의 크기
∙ futile = 버려진 염색체 수
∙ Max_futile = 염색체가 버려질 수 있는 최대 횟수
∙ pRmi = random mutation inherit 함수의 교환확률
∙ limitdist = 염색체간 최소 거리
먼저 각 파라미터를 초기화를 하고, MMR(Maximum Marginal Return)을 수행하여 solutionMMR 값을 얻는다. MMR을 통해 얻은 해는 전반적으로 우성의 유전자를 갖게 된다. 그런 다음 random generator를 이용하여 k번째 염색체를 생성한다. 생성된 염색체와 solutionMMR값을 random mutation inherit을 수행하여 새로운 k번째 염색체를 생성한다. 만약 현 iteration에서 새롭게 생성된 k 번째 염색체와 다른 염색체와 거리가 limitdist보다 작을 경우 생성된 k번째 염색체는 버려지고 futile값을 증가시킨다.
futile값이 Max_futile값을 넘어가게 되면 알고리즘은 종료를 하고 만약 popSize만큼 염색체가 생성되지 않았다면 나머지 염색체들은 random generator를 이용하여 생성된다. 따라서 Max_futile의 값을 적절히 여유있게 설정하지 않는다면 쉽게 알고리즘이 종료될 수 있다. 새롭게 생성된 k번째 염색체와 모든 다른 염색체와의 거리가 limitdist보다 크면 해당 염색체는 population의 k번째 염색체로 적용하고, k값을 증가시킨다. popSize만큼 염색체가 생성된다면 종료한다. MMR을 초기화에 적용하기 위해 제안하는 알고리즘 함수는 표 2와 같으며 random mutation inherit라 정의한다.
이렇게 Population 초기화를 수행하면서 MMR에서 얻은 우성 유전자를 염색체로 상속시키게 되고, limitdist만큼 각 염색체간의 거리를 조절하여 특정 탐색 영역에 염색체들이 몰리는 것을 방지하여 문제공간에서의 탐색영역을 넓힐 수 있다.
표 2. Random Mutation Inherit Pseudo Code
Table 2. Pseudo Code of Random Mutation Inherit
Algorithm Random Mutation Inherit for population initialization
1: Input : A old chromosome, A solutionMMR, a is probability of inherit
2: Output : A new chromosome
3: for all such that 1 <
Translation - English Improved WTA problem solving method using a parallel genetic algorithm which applied the RMI initialization method
1. Introduction
The problem of Weapon Target Allocation (WTA) is to find an optimum solution to minimize the damage of our assets from the target of an enemy offending us, or to assign the defense weapon system to enemy’s targets to maximize the kill probability toward each target. The WTA problem is a traditional NP-Complete problem and there have been many attempts to solve the WTA problem by using the various optimization algorithms. The heuristic algorithm is to choose one solution randomly and improve the solution one by one to find the near optimum solution, and can be used to solve the WTA problem. Traditionally, ACO (Ant Colony Optimization)[10], Simulated annealing[14], TABU search[12, 13], PSO(Particle Swarm Optimization)[11], and Genetic algorithm (GA) are used to solve the problem.
The GA is an algorithm to solve a problem with disperse and continuous variables using the meta-heuristic method. The GA is an evolutionary algorithm [6] to find an optimum solution or “near optimum” solution by forming a population consisting of many individuals by means of the genetic operator such as crossover, mutation etc. through evolution of the value over many generations.
The WTA problem is a problem in the war zone. The characteristics of the war zone are continuous changed target, target’s changing threat risk and real time response requirement which requires response in a short time. Under this war zone situation, it is most important to find a global optimum solution in a short time. Therefore, in this paper, we propose the novel parallel genetic algorithm using the RMI population initialization method. The proposed algorithm uses the improved initialization method and a parallel genetic algorithm which is applied efficiently to solve the WTA problem through two steps in order to improve search performance. Moreover, since our proposal can search a problem space of wide areas quickly, quality global solution can be obtained. Our proposed algorithm has a better performance compared with previous WTA problem solving algorithms, and since the high quality global optimum solution can be obtained, it can build a WTA system which can respond to enemy’s attack in real time.
2. Related Works
2.1 WTA Problem
The WTA problem is also called Weapon Allocation or Weapon Assignment. It is to assign weapons in response to a confirmed attack by a weapon system [2]. Generally, it is to find optimum weapon allocation which minimizes the threat risk of the targets by assigning offensive weapons towards the targets. Simply to say, the WTA problem can be specified to minimize the value of the function in the below equation (1)
(1)
The constraint is the below equation (2).
(2)
Here, variable can be defined as a binary variable according to the below equation (3).
(3)
From the equation (1), variable is a set of our weapon ( ) and is a set of the approaching targets. is a probability that weapon k can kill target i, and is a threat value for target i. In addition, each of our weapon must be assigned to one target. The WTA problem defined as this is called the Static Target-Based Weapon Allocation.
Here, solution is expressed as below. Each value of the matrix is either 0 or 1. 1 means that the weapon in the corresponding column is assigned to the target in the corresponding row.
2.2 GA Initialization Problem
The initialization of a GA population is a process of creating an initial chromosome population which can be filled with random numbers by using a random number generator. However, this population initialization process is a process of creating a problem space which can be searched by the GA algorithm. The performance and efficiency of the GA can be dependent on the layout of chromosome in the space [3].
There are two considerations largely in the initialization problem, one is how much search space is distributed in the problem space and the other is how fast inducing a good solution. These two considerations have conflict attribute to each other.
The problem of distribution of the search space is a problem of how to distribute search space (chromosome) in the problem space widely and efficiently. If the formation of search space is wrong in the Global Optimization problem, the global optimum cannot be searched so that the better solution cannot be found (incorrect design of the genetic operator or incorrect setup of the gene parameter or incorrect chromosome expression can affect too). This will cause incorrect convergence to the Local Optimum. In that case, we may have incorrect convergent solution which is not the near-optimum solution.
The problem of inducing the better solution quickly is to apply the domain knowledge rather than using meaningless random number during the population initialization, or to apply a fast search algorithm to attract the first search space near the near-optimum solution thereby inducing to find the optimum solution within that area. In terms of the conceptual principle of the gene algorithm, when the initial chromosome population is formed, a good solution can be found quickly using the dominant characteristics by applying the population to the chromosome which has good gene heredity (dominant gene).
Such two considerations should be considered carefully while using gene algorithms according to the domain’s characteristics and limitations. In this paper the weapon assignment problem should assign the weapons as quickly as possible, and must assign the weapons within the limited time when enemy’s attack occurs. Therefore, during the initial population generation, it is advantageous to induce near optimum solution quickly by distributing dominant genes in the initial population using the domain’s knowledge or local search method.
2.3 Parallel Gene Algorithm
The gene algorithm is a algorithm which find the optimum solution by performing repeatedly a gene operator consisting of selection, cross, and mutation. As the operation runs, it converges to one optimum solution gradually. This gene algorithm has large amount of calculation due to its repetitive operations of many numbers over many generations, and takes much time to finish. To solve this problem, the parallel gene algorithm is introduced to perform gene operators in parallel by using the many sub-populations [ADA 94, GOR 93, LIN 94].
There are three forms in the parallel gene algorithm in general as follows: (1) global single-population master-slave GAs, (2) single-population fine-grained, and (3) multiple-population coarse-grained GAs.
In the master-slave GA method, the master performs the gene operator and the slave simply calculates the value of fitness by distributing individuals. The fine-grained GA method is good for the massively parallel computer, which configures the space-structure population. Selection and cross is limited to performing with only neighbor populations, it permits interaction between neighbor’s all individuals.
The coarse-grained parallel processing method is to divide populations into sub-population in which gene operators are applied independently so that the sub-population is the same as the sequential evolution operation. The difference between them is an exchange of population. This is called migration. The parameters in the coarse-grained algorithm are recombination, mutation operation, selection and migration. Prettey [12] proposed that recombination, mutation operation and selection in this method, which occur individually in the sub-population, have the same effect eventually as the sequential evolution operation. The migration can be categorized into migration rate and migration interval. The migration rate is the amount of population to be migrated and the migration interval is a frequency of the migration. In this paper, we proposed the improved multiple-population GA method using the RMI initialization method.
3. Parallel Gene Algorithm using the RMI Initialization Method
3.1 RMI Initialization Method
In this paper, we propose to improve the performance of the gene algorithm in the area of the WTA problem by initializing the population efficiently. The proposed initial algorithm is as follows. The parameters used in the algorithm are as follows:
∙ popSize = the size of population
∙ futile = the number of futile chromosome
∙ Max_futile = Maximum number of futile chromosome ∙ pRmi = the exchange probability in the random mutation inherit function
∙ limitdist = Minimum distance between chromosomes
First, the parameters are initialized, and the value of solutionMMR is obtained by performing MMR (Maximum Marginal Return). The solutions through MMR have dominant genes in general. Next, using a random generator, k-th chromosome is generated. A new k-th chromosome is generated by performing random mutation inherit with the generated chromosome and the value of solutionMMR. If a distance between the newly generated k-th chromosome which is generated in the current iteration and other chromosome is less than limitdist, then the generated k-th chromosome is futile and the futile value is increased.
If the futile value is larger than the Max_futile value, the algorithm stops, and if the number of chromosome generated is less than popSize, other chromosomes are generated by using a random generator. Therefore, if the Max_futile number is not set properly, the algorithm can stop quickly. If a distance between the newly generated k-th chromosome and other chromosomes is more than limitdist, the corresponding chromosome is applied to the k-th chromosome in the population and the value of k is increased. If the number of chromosome reaches popSize, the algorithm stops. The proposed algorithm function to apply the MMR to the initialization is shown in Table 2 and is defined as the random mutation inherit.
The dominant genes which are obtained by performing MMR during the population initialization are inherited to the chromosomes, and the search area in the problem space can be expanded by preventing chromosome from gathering in the specific search area using controlling the distance between the chromosomes to make it the same as limitdist.
Table 2. Random Mutation Inherit Pseudo Code
Table 2. Pseudo Code of Random Mutation Inherit
Algorithm Random Mutation Inherit for population initialization
1: Input : A old chromosome, A solutionMMR, a is probability of inherit
2: Output : A new chromosome
3: for all such that 1 <
More
Less
Translation education
PhD - Otago University
Experience
Years of experience: 31. Registered at ProZ.com: Jun 2012.
Portfolio