Add a parallel algorithm to improve the performance of TPE with large concurrency

[PurityFan]

What would you like to be added: When the number of concurrencies is large, the points selected by the TPE will be concentrated, we will add excellent parallel algorithms to solve this problem.

Why is this needed: Better usage of computing resource

Components that may involve changes: A new algorithm to handle parallel TPE and related doc

[Crysple]

I've run experiments on some test functions with different experimental configuration ( trial concurrency, constant_liar_type etc.).

Experiment on Ackley Function

Ackley Function

• There are only two args in the Ackley Function. Denote them as x and y, then the function is:
  

• Its global optimum point is:

  

• An image on it might be:

Experiment

Setup

Two contrast experiments: Exp 1 with Exp 2 and Exp 3 with Exp 4 to see if there's any improvement.

	Max Trial Num	Trial Concurrency	Parallel_Optimize	Constant_liar
Exp 1	160	20	True	min
Exp 2	160	20	False (original TPE)	/
Exp 3	400	50	True	min
Exp 4	400	50	False (original TPE)	/

Result

Exp 1 and Exp 2

• Exp 1 (new TPE with min)

  • Internal WebUI: http://10.214.70.99:8020/oview

  • Top 10
    

  • Distribution of Sampled Points
    

• Exp 2 (old TPE)

  • Internal WebUI: http://10.214.70.99:8019/oview

  • Top 10
    

  • Distribution of Sampled Points
    

Exp 3 and Exp 4

• Exp 3 (new TPE with min)

  • Internal WebUI: http://10.214.70.99:8051/oview

  • Top 10
    

  • Distribution of Sampled Points
    

• Exp 4 (old TPE)

  • Internal WebUI: http://10.214.70.99:8050/oview
  • Top 10
    
  • Distribution of Sampled Points
    

In this experiment on Ackley Function, TPE in parallel mode tends to explore more and find a better 'best result'.
Besides, It can be seen that in the new version of TPE, the distribution of the sampled points is more even

Strange Phenomenon

With parallel optimize mode on, starting from the second trial, TPE will generate several trial configurations that are totally the same. This might be a potential bug.

Experiment on Rastrigin Function

Rastrigin Function

• On an n-dimensional domain it is defined by:

  

  where A=10 and x_{i} in [-5.12,5.12]. It has a global minimum at X = 0 where f(X)=0.

• Plot on this function

Experiment

Setup

	Max Trial Num	Trial Concurrency	Parallel_Optimize	Constant_liar
Exp 1	400	20	True	min
Exp 2	400	20	False (original TPE)	/
Exp 3	1000	20	True	min
Exp 4	1000	20	False (original TPE)	/
Exp 5	1000	50	True	min
Exp 6	1000	50	False (original TPE)	/

Result

Exp 1 and Exp 2

Exp 3 and Exp 4

Exp 5 and Exp 6

• Exp 5
  
  

• Exp 6
  
  

[scarlett2018]

• Need an option to switch between parallel model and non-parallel model

[suiguoxin]

solved in #1373