1
$\begingroup$

The multi-objective optimization problem in my case is defined below:

  • Objective 1: Minimize $f_1(X_1,X_2)=C_1X_1+C_2X_2+C_3X_1^2+C_4X_2^2+C_5X_1^2X_2^2$

  • Objective 2: Minimize $f_2(X_1,X_2)=D_1X_1+D_2X_2+D_3X_1^2+D_4X_2^2+D_5X_1^2X_2^2$

  • Objective 3: Minimize $f_3(X_2)=-E_1X_2$

  • Constraint 1: $ 0 \le X_1 \le A_1$

  • Constraint 2: $ 0 \le X_2 \le A_2$

  • Constraint 3: $ X_1 + X_2 \le A_3$

Here, $C_1,C_2,C_3,C_4,C_5,D_1,D_2,D_3,D_4,D_5,E_1,A_1,A_2$ and $A_3$ are positive constant numbers. $X_1$ and $X_2$ are decision variables.

I have used a real-coding method for chromosome coding and used NSGA-II for optimization. I used NSGA-II since it is the most commonly adopted method for arriving at a Pareto front. However, to use NSGA-II, is it always required to prove the NP-Hardness of a problem?

To calculate the computational complexity of a NSGA-II problem, we need to calculate both the complexity for each generation and the number of generations[1].

Let's say that the complexity is $\mathcal O(G\cdot F\cdot P^2)=\mathcal O(100\cdot3\cdot100^2)$. Here, $G$ is number of generations, $F$ is the number of objective functions, and $P$ is the population size.

How do we justify the use of NSGA-II in this case?

Reference

[1] Curry, D. M., Dagli, C. H. (2014). Computational Complexity Measures for Many-objective Optimization Problems. Procedia Computer Science. 36:185-191.

Improve this question
$\endgroup$
7
  • $\begingroup$ Are the objectives all convex functions? $\endgroup$
    – Qurious Cube
    Commented Jun 30, 2021 at 18:44
  • $\begingroup$ If i did the math correctly, the determinant of the hessian of objective 2 is $4a^{2}u^{2}v^{2} + 4acv^{2} + 4abu^{2} + 4bc - 16a^{2}u^{2}v^{2}$ where $a = D_5$, $b=D_3$, $c = D_4$, $u = X_{1}$, $v = X_{2}$. The objective function is convex at the points $(u, v)$ if this determinant is positive and $2av^{2} + 2b > 0$ ... If the objective is convex within your other constraints, then it is good news. Unlikely, but I don't know the values of your constants. The feasible region is convex because it is the intersection between a rectangle and the area under a line. $\endgroup$
    – Qurious Cube
    Commented Jun 30, 2021 at 19:17
  • 1
    $\begingroup$ I agree with Michael's comment at math.stackexchange.com/questions/4187024/… too. The objectives are smooth and simple. I think evolution algorithm looks like an overkill. $\endgroup$
    – Qurious Cube
    Commented Jun 30, 2021 at 19:27
  • $\begingroup$ Cross-posted widely: math.stackexchange.com/q/4187024/14578, or.stackexchange.com/q/6518/2415, mathoverflow.net/q/396528/37212, cstheory.stackexchange.com/q/49192/5038. Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Commented Jun 30, 2021 at 23:16
  • $\begingroup$ Please ask only one question per post. You have asked two different questions in the body of your post, and a third one in the title. Please pick one question to ask; if you want to ask multiple questions, ask them in separate posts. Please define exactly what you mean by solving this multi-objective problem: do you want to enumerate all solutions on the Pareto front? to find one Pareto-optimal solution? to find a solution that trades off all of the objective functions somehow (and if so, how do you want to manage and formalize that tradeoff)? $\endgroup$
    – D.W.
    Commented Jun 30, 2021 at 23:18

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.