jmetal 4.5 - Chapter 3
주요 객체들
- Algorithm
- Problem
- SolutionSet
- Solution
- Operator
main components and their relationships is depicted in Figure 3.1
ㅁ Encoding of Solutions
- Representation strongly depends on the problem and determines the operations that can be applied.
예) RealSolutionType class used to characterize solutions composed only by real variables.
Q. 마치 Type 변수가 있고 Type이 있는것처럼 solutoin type 들을 루즈하게 커플링해 놓은 이유는?
A. interesting point of using solution types is that it is very simple to define more complex representations, mixing different variable types.
For example, if we need a new solution representation consisting in a real, an integer, and a permutation of integers, a new class extending SolutionType can be defined for representing the new type, where basically only the createVariables() method should be redefined.
밑에 이어서 creataVariables() 메소드도 있다.
Q. 만약에 soultion Type이 Real이 아닌 새로운 type의 솔루션을 만들고 싶다면?
A. creataVariables() 메소드를 새롭게 정의해주어야 한다.
3.1.2 Operators
- Metaheuristic techniques are based on modifying or generating new solutions from existing ones by means of the application of different operators. (E.g., EA alogrithm -->Crossover opeartor for modifying solutoin)
- The framework already incorporates a number of operators, which can be classified into 4 different classes:
- Crossover
- Mutation
- Selection
- Local Search
- Each operator contains the setParameter() and getParameter() methods, which are used for adding and accessing to an specific parameter of the operator.
- For example, the SBX crossover requires two parameters, a crossover probability (as most crossover operators) plus a value for the distribution index (specific of the operator). The operators can also receive their parameters by passing them as an argument when the operator object is created
operator는 특정 solutoin type에만 적용될 수 있다. 따라서 Thus, we can define, for example, a unique two-points crossover operator that can be applied to binary and real solutions, using the solution type to select the appropriate code in each case.
The way of creating and setting the SBX crossover operator is depicted in Listing 3.3
- This has two parameters: crossover probability & distribution index.
1) Java HashMap : a map having pairs (name, object) for storing the operator parameters (line 3), (lines 6-7)
2) Operator is created (line 10)
- CrossOver에도 여러 종류가 있어서 첫번째 파라미터에 SBXCrossover를 넘겨주었다.
3) Operator is added to an algorithm (line 13)
Q. SBXCrossover에다가 이름을 "crossover"라고 붙여준건가?
방금 만든 operator 이용하는 방법
1) get the previously created operator (line 5)
2) In the case of the SBX crossover operator, the parameters are two solutions previously obtained (selection operator에 의해서 얻어진 2개의 솔루션) (lines 8-9).
3) result is a another pair of solutions, (line 10)
ㅁ 내부 구현 - The implementation of the SBX crossover operator
1)2 parameters characterizing the operator (crossover probability and distribution index) are declared in (lines 8-9)
2) 주목!! An operator can be applied to a given set of encodings, so the adopted approach is to indicate in a list the valid solution types. (lines 14-15)
아까도 말했듯이 특정 operator는 허용된 데이터 타입이 정해져 있다.
In the case of the SBX crossover, the operator is intended to Real and ArrayReal solution types, so they are included in the list called VALID TYPES. Later, this list is used in the execute() method to check that the solutions to be combined have the correct representation
(lines 19-26) The constructor merely gets the map received as argument and checks whether some of the parameters have to be set
- The execute() method receives as a parameter a generic Java Object (line 37), which must represent an array of two solutions, the parent solutions (line 38).
- We can see in lines 46-51 how the VALID TYPES is used to check that the parent solutions have valid encodings.
아까도 말했듯이 operator는 적용될 수 있는 type이 정해져있다.
- Finally, the method calls a function doCrossover() (line 54) which actually performs the crossover and returns an array with the two new generated solutions, with are the return object of the method (line 56).
3.1.3 Problems
- All the problems inherits from class Problem
- This class contains two basic methods: evaluate() & evaluateConstraints()
- Both methods receive a Solution representing a candidate solution to the problem;
- evaluate() : evaluates Solution
- evaluateConstraints() determines the overall constraint violation of this Solution.
All the problems have to define the evaluate() method, while only problems having side constraints need to define evaluateConstraints(). The constraint handling mechanism implemented by default is the one proposed in [6]
- A key design feature in jMetal : the problem defines the allowed solutions types that are suitable to solve it.
(어떻게보면 당연하다.)
예제) Kursawe’s problem
- 5: Kursawe’s problem extends class Problem
- 9-28 : constructor
- The basic features of the problem (number of variables, number of objectives, and number of constraints) are defined in lines 10-12.
- The limits of the values of the decision variables are set in lines 15-21.
- The sentences between lines 23-27 are used to specify that the allowed solution representations are binarycoded real and real, so the corresponding SolutionType objects are created and assigned to a state variable.
- (lines 33-43); After the constructor, the evaluate() method is redefined ; in this method, after computing the two objective function values, they are stored into the solution by using the setObjective method of Solution (lines 41 - 42)
이외에도.. Many of commonly used benchmark problems are already included in jMetal. Examples are the ones proposed by Zitzler-Deb-Thiele (ZDT) [42], Deb-Thiele-Laumanns-Zitzler (DTLZ) [5], Walking-FishGroup (WFG) test problems [16]), and the Li-Zhang benchmark [22].
3.1.4 Algorithms
The last core class in the UML diagram in Fig. 3.1 to comment is Algorithm, an abstract class which must be inherited by the metaheuristics included in the framework. In particular, the abstract method execute() must be implemented; this method is intended to run the algorithm, and it returns as a result a SolutionSet
- Solution set은 Population이거나, 혹은 약간 그 history 그런 느낌인듯. ㅇㅇ맞음..
- An instance object of Algorithm may require some application-specific parameters, that can be added and accessed by using the methods addParameter() and getParameter(), respectively. Similarly, an algorithm may also make use of some operators, so methods for incorporating operators (addOperator()) and to get them (getOperator()) are provided.
- A detailed example of algorithm can be found in Section 3.3, where the implementation of NSGA-II is explained.
3.3 Case Study: NSGA-II
- NSGAII inherits from Algorithm ( This class has an abstract method, execute(), that is called to run the algorithm and returns as a result a SolutionSet (typically, a population or archive containing the obtained approximation set).
- 알고리즘에 새로운 Operator 추가 가능. We can see that new operators can be added to an algorithm with the method addOperation();
- 기존에 있는 built-in Operator는 getOperation() 이용: these operations are accessed in the algorithm by invoking getOperation()
- we can pass parameters to an algorithm (methods setInputParameter() and getInputParameter),
- algorithm can return output results via setOutputParemeters() and getOutputParameters.
- NSGAII has a constructor which receives the problem to solve as a parameter, as well as the implementation on execute()
ㅁ jMetal에 구현된 NSGAii 클래스 (file jmetal/metaheuristics/nsgaII/NSGAII.java)의 구현을 뜯어보자.
- 코드의 기본구조
코드 구조는 위와 같고 실제 내부구현은 다음과 같다. 먼저 execute()
- The parameters to store the population size and the maximum number of evaluations are declared in lines 2-3.
- The next variable, evaluations, is a counter of the number of computed evaluations. The objects declared in lines 6-7 are needed to illustrate the use of quality indicators inside the algorithms; (we will explain their use later);
- lines 10-12 contain the declaration of the populations needed to implement NSGA-II:
the current population, an offspring population, and an auxiliary population used to join the other two.
- Next, we find the three genetic operators (lines 14- 16) and a Distance object (from package jmetal.util), which will be used to calculate the crowding distance.
이어서
- Once we have declared all the needed objects, we proceed to initialize them (Listing 3.9).
- The parameters populationSize and maxEvaluations are input parameters whose values are obtained in lines 23-24;
the same applies to indicators, although this parameter is optional (the other two are required).
- The population and the counter of evaluations are initialized next (lines 28-29),
- finally the mutation, crossover, and selection operators are obtained (lines 34-36)
이어서
The initial population is initialized in the loop included in Lisrting 3.10. We can observe how new solutions are created, evaluated, and inserted into the population
The main loop of the algorithm is included in the piece of code contained in Listing 3.11.
- We can observe the inner loop performing the generations (lines 55-71), where the genetic operators are applied.
- The number of iterations of this loop is populationSize/2 because it is assumed that the crossover returns two solutions; 만약에 in the case of using a crossover operator returning only one solution, the sentence in line 55 should be modified accordingly.
이어서
After the offspring population has been filled, the next step in NSGA-II is to apply ranking and crowding to the union of the current and offspring populations to select the new individuals in the next generation.
- Listing 3.13 illustrates the use of quality indicators inside a metaheuristic.
In particular, it shows the code we used in [29] to study the convergence speed of multi-objective metaheuristics. As we commented before, if the indicator object was specified as input parameter (otherwise, it would be null - line 120), we apply it to test whether the hypervolume of the new population, at the end of each generation, is equal of greater than the 98% of the hypervolume of the true Pareto front (see [29] for further details).
- In case of success, the variable requiredEvaluations is assigned the current number of function evaluations (line 124). Once this variable is not zero, we do not need to carry out the test any more; that is the reason of including the condition in line 121
The last sentences of the execute() method are included in Listing 3.14.
- In line 129 we can observe that the variable requiredEvaluations is returned as an output parameter.
- Finally, we apply ranking to the resulting population to return only non-dominated solutions (lines 132-133).
3.3.2 Class NSGAII main
- 앞서서는 NSGAII 알고리즘을 보았고 여기선 In this section we describe the NSGAII main.java program
- The file is located in jmetal/metaheuristics/nsgaII, as it is indicated in line 22 in the piece of code included in Listing 3.15,
- The logging classes (lines 39-40) are needed to use a logger object, which allows us to log error messages
- Listing 3.17 contains the code used to declare the objects required to execute the algorithm (lines 59-63).
- The logger object is initialized in lines 69-72, and the log messages will be written in a file named ”NSGAII main.log”.
- The sentences included between lines 74 and 92 process the arguments of the main() method.
- The default problem to solve is indicated after line 85
- This is the only argument needed to create an instance of the algorithm, as we can see in line 94
- Once an object representing the algorithm to run has been created, it must be configured. In the code included in Listing 3.18, the input parameters are set in lines 97-98,
- the crossover and mutation operators are specified in lines 101-109,
- the selection operator is chosen in line 113
- Once the operators have been specified, they are added to the algorithm object in lines 116-118.
- The sentence in line 121 sets the indicator object as input parameter.
- When the algorithm has been configured, it is executed by invoking its execute() method (line 125 in Listing 3.19). - When it has finished, the running time is reported, and the obtained solutions and their objectives values are stored in two files (lines 131 and 133).
- Finally, if the indicator object is not null, a number of quality indicators are calculated (lines 136-141) and printed, as well as the number of evaluations returned by the algorithm as an output parameter.
jmetal 패키지구조에 대한 설명은 생략했음.
