search

Project-Platypus / Platypus

A Free and Open Source Python Library for Multiobjective Optimization
GNU General Public License v3.0
570 stars 153 forks source link

Potential issues when computing objectives and hypervolume value on individual objectives #16

Closed ivan-marroquin closed 7 years ago

ivan-marroquin commented 7 years ago

Hi David,

I sent you a copy of a script that I am using to determine how many iterations take to get a pareto front that is - as much as possible - close to the optimal point. For that, I am using the NSGAII with UNDX and a population size of 100.

At each iteration, I compute the hypervolume for each individual objective and record the result. I looked for the objective with the smallest hypervolume value, to select it as the best objective for a given iteration.

I noticed the following issues: 1) Starting from iteration 6000, the algorithm produces the same objective with an hypervolume value of 0. When I examine the output file, none of the objectives have a hypervolume value of 0. Additionally, there are less and less number of objectives that are generated

2) The script ends with this error: Run iteration : 18000

Traceback (most recent call last):

File "", line 1, in runfile('C:/Users/IMarroquin/Documents/My Python Scripts/Optimization_MLP_Clusters/Platypus_Test_Optimization.py', wdir='C:/Users/IMarroquin/Documents/My Python Scripts')

File "C:\Temp\Anaconda3\lib\site-packages\spyder\utils\site\sitecustomize.py", line 880, in runfile execfile(filename, namespace)

File "C:\Temp\Anaconda3\lib\site-packages\spyder\utils\site\sitecustomize.py", line 102, in execfile exec(compile(f.read(), filename, 'exec'), namespace)

File "C:/Users/IMarroquin/Documents/My Python Scripts/Optimization_MLP_Clusters/Platypus_Test_Optimization.py", line 466, in algorithm.run(iter)

File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\core.py", line 302, in run self.step()

File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\algorithms.py", line 175, in step self.iterate()

File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\algorithms.py", line 196, in iterate offspring.extend(self.variator.evolve(parents))

File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\operators.py", line 410, in evolve result.append(self.undx(parents))

File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\operators.py", line 446, in undx e = orthogonalize(d, e_eta)

File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\tools.py", line 55, in orthogonalize u = subtract(u, project(u, v))

File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\tools.py", line 51, in project return multiply(dot(u, v) / dot(v, v), v)

ZeroDivisionError: float division by zero

I attached the script and the data that I am using for your convenience - hoping this helps. Please note that Platypus related code begins at line 241.

Kind regards, Ivan Potential_Issues.zip

dhadka commented 7 years ago

Hi, thanks for reporting these issues.

For the 0 hypervolume, I believe there are two issues at play. First, I believe you want to use argmax instead of argmin, since the best hypervolume has the largest value:


ind= np.argmax(extract_hypervolume_ind)

Second, NSGA-II doesn't perform well on many-objective problems (4+ objectives). Something called "deterioration" occurs with MOEAs using Pareto dominance to drive selection. As the number of objectives increases, it's more likely that offspring are non-dominated and you lose selection pressure. As a result, the MOEA can't select "better" offspring since they are nearly always non-dominated. I would recommend trying MOEA/D, Epsilon-MOEA, or Epsilon-NSGA-II, which are better at handling many-objective problems.

I believe the ZeroDivisionError is occurring when the selected parents for UNDX have duplicates. I'll have to check to see if we guard against that case. Out of curiosity, is there a reason you're using UNDX over the default of SBX and PM?

ivan-marroquin commented 7 years ago

Hi David,

Thanks for your prompt answer.

With respect to 0 hypervolume. My first approach was to compute the largest value - as you pointed out. Then, I changed mind because if I want to find the objective (among a set of solutions) with the smallest size of the space enclosed between the objective and the reference point (which is 0). Now, I am confused. In your experience, what do you suggest?

I am still learning and reading about MOEAs. I appreciate your advice regarding "deterioration". I will run tests including the other MOEAs algorithms that you mentioned.

For UNDX, I just decided to start the tests with this operator. Certainly, I will run tests using PMX, SBX, and PCX.

By the way, do you have references about these operators? Also, what reference did you use to implement hypervolume indicator?

Many thanks,

Ivan

dhadka commented 7 years ago

Take a look at https://github.com/MOEAFramework/MOEAFramework/releases/download/v2.12/MOEAFramework-2.12-BeginnersGuidePreview.pdf. This is for a different project, but it provides information about the algorithms and operators. For example, the operators are listed in Appendix C. (Note that not all of these operators/algorithms are available in Platypus; some are only in the Java code).

ivan-marroquin commented 7 years ago

Hi David,

I ran more tests, here are the results:

A) replace line 265 with: algorithm= IBEA(problem, population_size= 100, variator= SPX())

Run iteration IBEA: 4000 Traceback (most recent call last): File "", line 1, in runfile('C:/Users/IMarroquin/Documents/My Python Scripts/Optimization_MLP_Clusters/Platypus_Test_Optimization.py', wdir='C:/Users/IMarroquin/Documents/My Python Scripts') File "C:\Temp\Anaconda3\lib\site-packages\spyder\utils\site\sitecustomize.py", line 880, in runfile execfile(filename, namespace) File "C:\Temp\Anaconda3\lib\site-packages\spyder\utils\site\sitecustomize.py", line 102, in execfile exec(compile(f.read(), filename, 'exec'), namespace) File "C:/Users/IMarroquin/Documents/My Python Scripts/Optimization_MLP_Clusters/Platypus_Test_Optimization.py", line 619, in algorithm.run(iter) File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\core.py", line 302, in run self.step() File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\algorithms.py", line 67, in step self.iterate() File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\algorithms.py", line 1321, in iterate self.fitness_evaluator.evaluate(self.population) File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\core.py", line 1094, in evaluate normalize(solutions) File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\core.py", line 1071, in normalize raise PlatypusError("objective with empty range") PlatypusError: objective with empty range

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ B) Replace line 265 with: algorithm= IBEA(problem, population_size= 100, variator= SBX())

Note that this run gave hypervolume values of 0; however the objectives are non-zero. Is this a correct output?

Run iteration IBEA: 5000 compute the Hypervolume indicator on individual objectives and save results in a file Best hypervolume indicator given by : [ 0.96938169 0.96855789 0.2407836 0.52729565 1.0044533 -0.13265781 0.03024326 0.96853769] = 0.0 Elapsed time in seconds : 0.015600099999574013 End iteration IBEA: 5000

Run iteration IBEA: 6000 Traceback (most recent call last): File "", line 1, in runfile('C:/Users/IMarroquin/Documents/My Python Scripts/Optimization_MLP_Clusters/Platypus_Test_Optimization.py', wdir='C:/Users/IMarroquin/Documents/My Python Scripts') File "C:\Temp\Anaconda3\lib\site-packages\spyder\utils\site\sitecustomize.py", line 880, in runfile execfile(filename, namespace) File "C:\Temp\Anaconda3\lib\site-packages\spyder\utils\site\sitecustomize.py", line 102, in execfile exec(compile(f.read(), filename, 'exec'), namespace) File "C:/Users/IMarroquin/Documents/My Python Scripts/Optimization_MLP_Clusters/Platypus_Test_Optimization.py", line 619, in algorithm.run(iter) File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\core.py", line 302, in run self.step() File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\algorithms.py", line 67, in step self.iterate() File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\algorithms.py", line 1321, in iterate self.fitness_evaluator.evaluate(self.population) File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\core.py", line 1094, in evaluate normalize(solutions) File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\core.py", line 1071, in normalize raise PlatypusError("objective with empty range") PlatypusError: objective with empty range

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ C) Replace line 265: algorithm= MOEAD(problem, population_size= 100, variator= SBX())

Note that this run gave hypervolume values of 0; however the objectives are non-zero. Is this a correct output?

Run iteration MOEAD: 20000 compute the Hypervolume indicator on individual objectives and save results in a file Best hypervolume indicator given by : [ 0.96853828 0.96865851 0.21519858 0.52687126 0.98892325 -0.13335264 0.03328265 0.96861005] = 0.0 Elapsed time in seconds : 0.03120020000005752 End iteration MOEAD: 20000

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ D) Replace line 265 with: algorithm= SPEA2(problem, population_size= 100, variator= SBX())

Note that this run gave hypervolume values of 0; however the objectives are non-zero. Is this a correct output?

Run iteration SPEA2: 20000 compute the Hypervolume indicator on individual objectives and save results in a file Best hypervolume indicator given by : [ 1.7360276 0.97665167 0.95590794 0.53530258 0.98545378 -0.13228551 0.95270216 0.97705311] = 0.0 Elapsed time in seconds : 0.015600099999574013 End iteration SPEA2: 20000

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ E) Replace line 265 with: algorithm= EpsMOEA(problem, population_size= 100, epsilons= 0.05, variator= SBX())

I wonder if "population_size" parameter interfered with the technique. Is there a way to fix the population size for this technique (and also EpsNSGAII)?

Run iteration EpsMOEA: 20000 compute the Hypervolume indicator on individual objectives and save results in a file Best hypervolume indicator given by : [ 0. 0. 0. 0. 0. 0. 0. 0.] = 0.0 Elapsed time in seconds : 0.015600099999574013 End iteration EpsMOEA: 20000

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ F) Replace line 265 with: algorithm= PESA2(problem, population_size= 100, variator= SBX())

Run iteration PESA2: 1000

Traceback (most recent call last): File "", line 1, in runfile('C:/Users/IMarroquin/Documents/My Python Scripts/Optimization_MLP_Clusters/Platypus_Mini_test_optimization.py', wdir='C:/Users/IMarroquin/Documents/My Python Scripts') File "C:\Temp\Anaconda3\lib\site-packages\spyder\utils\site\sitecustomize.py", line 880, in runfile execfile(filename, namespace) File "C:\Temp\Anaconda3\lib\site-packages\spyder\utils\site\sitecustomize.py", line 102, in execfile exec(compile(f.read(), filename, 'exec'), namespace) File "C:/Users/IMarroquin/Documents/My Python Scripts/Optimization_MLP_Clusters/Platypus_Mini_test_optimization.py", line 279, in algorithm.run(iter) File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\core.py", line 302, in run self.step() File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\algorithms.py", line 1436, in step self.iterate() File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\algorithms.py", line 1452, in iterate parents = selector.select(self.variator.arity, self.archive) File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\core.py", line 187, in select return list(map(self.select_one, itertools.repeat(population, n))) File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\algorithms.py", line 1405, in select_one entry1 = self.draw() File "C:\Temp\Anaconda3\lib\site-packages\platypus-0.1-py3.6.egg\platypus\algorithms.py", line 1401, in draw key = self.grid.keys()[index]

TypeError: 'dict_keys' object does not support indexing

dhadka commented 7 years ago

I believe you're seeing 0 hypervolume because some of the objectives are negative whereas your minimum for hypervolume is 0. The hypervolume calculation is based on that found in the PISA library, and expects all points to lie between 0 and 1. If you change the minimum to include those negative values, you should start to see non-zero hypervolume.

The TypeError: dict_keys object does not support indexing error appears to be a Python 2/3 compatibility issue. Looks like PESA2 won't work on Python 3 until I can fix it.

Objective with empty range is a known issue with indicator-based algorithms like IBEA. If an objective is singular (e.g., every solution in the population has the same objective value or the difference is less than machine precision), then it's unable to normalize the objectives to calculate the indicator value.

ivan-marroquin commented 7 years ago

Thanks for the comments.

I read the guide for MOEAFramework. Bssed on Figure 1.5, it's much clear to me that I need to use np.argmax to choose the best objective among the set of solutions provided by a given algorithm. Thank you.

Since I need to solve several objective functions, I will focus only on those algorithms that perform well under this circumstance. Besides the algorithms: MOEA/D, Epsilon-MOEA, or Epsilon-NSGA-II. Is there another one in Platypus library that I should consider?