A two-phase variable neighborhood search for solving nonlinear optimal control problems

Iranian Journal of Numerical Analysis and Optimization

مقاله 2، دوره 5، شماره 1 - شماره پیاپی 7، تیر 2015، صفحه 13-36   

نوع مقاله: Research Article

شناسه دیجیتال (DOI): 10.22067/ijnao.v5i1.34200

نویسندگان

R. Ghanbari^{* 1}؛ A. Heydari²؛ S. Nezhadhosein³

¹Department of Applied Mathematics, Faculty of Mathematical Science, Ferdowsi University of Mashhad, Mashhad, Iran.

²Department of Applied Mathematics, Payame Noor University, Mashhad, Iran.

³Department of Applied Mathematics, Payame Noor University, Tehran, Iran.

چکیده

In this paper, a two-phase algorithm, namely IVNS, is proposed for solving nonlinear optimal control problems. In each phase of the algorithm, we use a variable neighborhood search (VNS), which performs a uniform distribution in the shaking step and the successive quadratic programming, as the local search step. In the first phase, VNS starts with a completely random initial solution of control input values. To increase the accuracy of the solution obtained from the phase 1, some new time nodes are added and the values of the new control inputs are estimated by spline interpolation. Next, in the second phase, VNS restarts by the solution constructed by the phase 1. The proposed algorithm is implemented on more than 20 well-known benchmarks and real world problems, then the results are compared with some recently proposed algorithms. The numerical results show that IVNS can find the best solution on 84% of test problems. Also, to compare the IVNS with a common VNS (when the number of time nodes is same in both phases), a computational study is done. This study shows that IVNS needs less computational time with respect to common VNS, when the quality of solutions are not different signifcantly.

کلیدواژه‌ها

Nonlinear optimal control problem؛ Variable neighborhood search؛ Successive quadratic programming

مراجع

1. Abo-Hammour, Z.S., Asasfeh, A.G., Al-Smadi, A.M. and Alsmadi, O.M.K. A novel continuous genetic algorithm for the solution of opti mal control problems, Optimal Control Applications and Methods, 32(4) (2011) 414–432.

2. Ali, M.M., Storey, C. and T¨orn, A. Application of stochastic global opti mization algorithms to practical problems, Journal of Optimization The ory and Applications, 95(3) (1997) 545–563.

3. Arumugam, M.S., Murthy, G.R. and Loo, C. K. On the optimal control of the steel annealing processes as a two stage hybrid systems via PSO algorithms, International Journal Bio-Inspired Computing, 1(3) (2009) 198–209.

4. Arumugam, M.S. and Rao, M.V.C. On the improved performances of the particle swarm optimization algorithms with adaptive parameters, cross over operators and root mean square (RMS) variants for computing op timal control of a class of hybrid systems, Application Soft Computing, 8(1) (2008) 324–336.

5. Atkinson, K. and Han, W. Theoretical Numerical Analysis: A Functional Analysis Framework, Texts in Applied Mathematics, Springer, 2009.

6. B¨uskens, C. and Maurer, H. SQP-methods for solving optimal control problems with control and state constraints: adjoint variables, sensitivity analysis and real-time control, Journal of Computational and Applied Mathematics, 120(1-2) (2000) 85–108.

7. Betts, J.T. Practical Methods for Optimal Control and Estimation Using Nonlinear Programming, Society for Industrial and Applied Mathemat ics, 2010.

8. Binder, T., Blank, L., Dahmen, W. and Marquardt, W. Iterative al gorithms for multiscale state estimation, part 1: Concepts, Journal of Optimization Theory and Applications, 111(3) (2001) 501–527.

9. Bonnans, J.J.F., Gilbert, J.C., Lemar´echal, C. and Sagastiz´abal, C.A. Numerical Optimization: Theoretical and Practical Aspects, Springer London, Limited, 2006.

10. Brimberg, J., Uroevi, D. and Mladenovi´c, N. Variable neighborhood search for the vertex weighted k-cardinality tree problem, European Jour nal of Operational Research, 171(1) (2006) 74 – 84.

11. Brimberg, J., Hansen, P. and Mladenovi´c, N. Attraction probabilities in variable neighborhood search, 4OR, 8(2) (2010) 181–194.

12. Bryson, A.E. Applied Optimal Control: Optimization, Estimation and Control, Halsted Press book’. Taylor & Francis, 1975.

13. Costa, W., Goldbarg, M. and Goldbarg, E. New VNS heuristic for total .owtime .owshop scheduling problem, Expert Systems with Applications, 39(9) (2012) 8149–8161.

14. Lopez Cruz, I.L., Van Willigenburg, L.G. and Van Straten, G. E.cient di.erential evolution algorithms for multimodal optimal control problems, Applied Soft Computing, 3(2) (2003) 97–122.

15. E.ati, S. and Saberi Nik, H. Solving a class of linear and non-linear optimal control problems by homotopy perturbation method, IMA Journal of Mathematical Control and Information, 28(4) (2011) 539–553.

16. Engelbrecht, A.P. Computational Intelligence: An Introduction, Wiley, 2007.

17. Fabien, B.C. Numerical solution of constrained optimal control problems with parameters, Applied Mathematics and Computation, 80(1) (1996) 43–62.

18. Fabien, B.C. Some tools for the direct solution of optimal control prob lems, Advances Engineering Software, 29(1) (1998) 45–61.

19. Fakharian, A., Beheshti, M.T.H. and Davari, A. Solving the Hamilton -Jacobian-Bellman equation using adomian decomposition method, Inter national Journal of Computer Mathematics, 87(12) (2010) 2769–2785.

20. Floudas, C.A. and Pardalos, P.M. Handbook of test problems in local and global optimization, Nonconvex optimization and its applications, Kluwer Academic Publishers, 1999.

21. Ghomanjani, F., Farahi, M.H. and Gachpazan, M.B´ezier control points method to solve constrained quadratic optimal control of time varying linear systems, Computational and Applied Mathematics, 31(2012) 433– 456.

22. Ghosh, A., Das, S., Chowdhury, A. and Giri, R. An ecologically inspired direct search method for solving optimal control problems with B´ezier pa rameterization, Engineering Applications of Arti.cial Intelligence, 24(7) (2011) 1195–1203.

23. Goh, C.J. and Teo, K.L. Control parametrization: A uni.ed approach to optimal control problems with general constraints, Automatica, 24(1) (1988) 13–18.

24. Gong, Q., Kang, W. and Ross, I.M. A pseudospectral method for the optimal control of constrained feedback linearizable systems, Automatic Control, IEEE Transactions on, 51(7) (2006) 1115–1129.

25. Hansen, P., Mladenovi´c, N. and P´erez, J. M. Variable neighbourhood search: methods and applications, 4OR, 6(4) (2008) 319–360.

26. Hansen, P., Mladenovi´c, N. and Uro.sevi´c, D. Variable neighborhood search and local branching, Computers and Operations Research, 33(10) (2006) 3034–3045.

27. Herrera, F. and Zhang, J. Optimal control of batch processes using particle swam optimisation with stacked neural network models, Computers and Chemical Engineering, 33(10) (2009) 1593–1601.

28. Johnson, A.W. and Jacobson, S.H. On the convergence of generalized hill climbing algorithms, Discrete Applied Mathematics, 119(1-2) (2002) 37–57.

29. Kirk, D.E. Optimal Control Theory: An Introduction, Dover Publica tions, 2004.

30. Vincent Antony Kumar, A. and Balasubramaniam, P. Optimal control for linear system using genetic programming, Optimal Control Applications and Methods, 30(1) (2009) 47–60.

31. Lee, M.H., Han, C. and Chang, K.S. Dynamic optimization of a continu ous polymer reactor using a modi.ed di.erential evolution algorithm, In dustrial and Engineering Chemistry Research, 38(12) (1999) 4825–4831.

32. Loudni, S., Boizumault, P. and Levasseur, N. Advanced generic neigh borhood heuristics for VNS, Engineering Applications of Arti.cial Intel ligence, 23(5) (2010) 736–764.

33. Mekarapiruk, W. and Luus, R. Optimal control of inequality state con strained systems, Industrial and Engineering Chemistry Research, 36(5) (1997) 1686–1694.

34. Michalewicz, Z., Janikow, C.Z. and Krawczyk, J.B. A modi.ed genetic algorithm for optimal control problems, Computers & Mathematics with Applications, 23(12) (1992) 83–94.

35. Mladenovi´c, N. and Hansen, P. Variable neighborhood search, Computers and Operations Research, 24(11) (1997) 1097–1100.

36. Mladenovi´c, N., Dra.zi´c, M., Kova.cevic-Vuj.ci´c, V. and Cangalovi´c, M. General variable neighborhood search for the continuous optimization, European Journal of Operational Research, 191(3) (2008) 753–770.

37. Modares, H. and Naghibi-Sistani, M.B. Solving nonlinear optimal control problems using a hybrid IPSO -SQP algorithm, Engineering Applications of Arti.cial Intelligence, 24(3) (2011) 476–484.

R. Ghanbari, A. Heydari and S. Nezhadhosein

38. Muhlenbein, H. and Zimmermann, J. Size of neighborhood more impor tant than temperature for stochastic local search, In Evolutionary Com putation, 2000. Proceedings of the 2000 Congress on, volume 2, pages 1017–1024 vol.2, 2000.

39. Nocedal, J. and Wright, S.J. Numerical Optimization, Springer series in operations research and .nancial engineering, Springer, 1999.

40. Rajesh, J., Gupta, K., Kusumakar, H.S., Jayaraman, V.K. and Kulka rni, B.D. Dynamic optimization of chemical processes using ant colony framework, Computers & Chemistry, 25(6) (2001) 583–595.

41. Saberi Nik, H., E.ati, S. and Yildirim, A. Solution of linear optimal control systems by di.erential transform method, Neural Computing and Applications, 23(5) (2013) 1311–1317.

42. Sarkar, D. and Modak, J.M. Optimization of fed-batch bioreactors using genetic algorithm: multiple control variables, Computers and Chemical Engineering, 28(5) (2009) 789–798.

43. Schlegel, M., Stockmann, K., Binder, T. and Marquardt, W. Dynamic optimization using adaptive control vector parameterization, Computers & Chemical Engineering, 29(8) (2005) 1731–1751.

44. Shi, X.H., Wan, L.M., Lee, H.P., Yang, X.W., Wang, L.M. and Liang, Y.C. An improved genetic algorithm with variable population-size and a PSO-GA based hybrid evolutionary algorithm, Machine Learning and Cybernetics, 2003 International Conference on, volume 3, pages 1735– 1740, 2003.

45. Sim, Y.C., Leng, S.B. and Subramaniam, V. A combined genetic algorithms-shooting method approach to solving optimal control problems,

International Journal of Systems Science, 31(1) (2000) 83–89.

46. Srinivasan, B., Palanki, S. and Bonvin, D. Dynamic optimization of batch processes: I. characterization of the nominal solution, Computers & Chemical Engineering, 27(1) (2003) 1 – 26.

47. Sun, F., Du, W., Qi, R., Qian, F. and Zhong, W. A hybrid improved genetic algorithm and its application in dynamic optimization problems of chemical processes, Chinese Journal of Chemical Engineering, 21(2) (2013) 144–154.

48. Marinus van Ast, J., Babu.ska, R. and De Schutter, B. Novel ant colony optimization approach to optimal control, International Journal of Intel ligent Computing and Cybernetics, 2(3) (2009) 414–434.

49. Vlassenbroeck, J. A chebyshev polynomial method for optimal control with state constraints, Automatica, 24(4) (1988) 499–506.

50. Wang, F.S. and Chiou, J.P. Optimal control and optimal time location problems of di.erential-algebraic systems by di.erential evolution, Indus trial and Engineering Chemistry Research, 36(12) (1997) 5348–5357.

51. Yaghini, M., Karimi, M. and Rahbar, M. A hybrid metaheuristic approach for the capacitated p-median problem, Applied Soft Computing, 13(9) (2013) 3922–3930.

52. Yamashita, Y. and Shima, M. Numerical computational method using ge netic algorithm for the optimal control problem with terminal constraints and free parameters, Nonlinear Analysis: Theory, Methods & Applica tions, 30(4) (1997) 2285–2290.

53. Zhang, B., Chen, D. and Zhao, W. Iterative ant-colony algorithm and its application to dynamic optimization of chemical process, Computers & Chemical Engineering, 29(10) (2005) 2078–2086.