×

zbMATH — the first resource for mathematics

A filter-based artificial fish swarm algorithm for constrained global optimization: theoretical and practical issues. (English) Zbl 1312.90066
Summary: This paper presents a filter-based artificial fish swarm algorithm for solving nonconvex constrained global optimization problems. Convergence to an \(\varepsilon\)-global minimizer is guaranteed. At each iteration \(k\), the algorithm requires a \((\rho^{(k)},\varepsilon^{(k)})\)-global minimizer of a bound constrained bi-objective subproblem, where as \(k\to\infty\), \(\rho^{(k)}\to 0\) gives the constraint violation tolerance and \(\varepsilon^{(k)}\to\varepsilon\) is the error bound defining the accuracy required for the solution. The subproblems are solved by a population-based heuristic known as artificial fish swarm algorithm. Each subproblem relies on the approximate solution of the previous one, randomly generated new points to explore the search space for a global solution, and the filter methodology to accept non-dominated trial points. Convergence to a \((\rho ^{(k)},\varepsilon^{(k)})\)-global minimizer with probability one is guaranteed by probability theory. Preliminary numerical experiments show that the algorithm is very competitive when compared with known deterministic and stochastic methods.

MSC:
90C26 Nonconvex programming, global optimization
90C59 Approximation methods and heuristics in mathematical programming
Software:
ipfilter; Ipopt
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aguirre, AH; Rionda, SB; Coello Coello, CA; Lizrraga, GL; Montes, EM, Handling constraints using multiobjective optimization concepts, Int. J. Numer. Methods Eng., 59, 1989-2017, (2004) · Zbl 1060.74581
[2] Akay, B; Karaboga, D, Artificial bee colony algorithm for large-scale problems and engineering design optimization, J. Intell. Manuf., 23, 1001-1014, (2012)
[3] Ali, MM; Golalikhani, M, An electromagnetism-like method for nonlinearly constrained global optimization, Comput. Math. Appl., 60, 2279-2285, (2010) · Zbl 1205.90270
[4] Ali, MM; Kajee-Bagdadi, Z, A local exploration-based differential evolution algorithm for constrained global optimization, Appl. Math. Comput., 208, 31-48, (2009) · Zbl 1159.65058
[5] Ali, M.M., Zhu, W.X.: A penalty function-based differential evolution algorithm for constrained global optimization. Comput. Optim. Appl. 54(3), 707-739 (2013) · Zbl 1295.90050
[6] Audet, C; Dennis, JE, A pattern search filter method for nonlinear programming without derivatives, SIAM J. Optim., 14, 980-1010, (2004) · Zbl 1073.90066
[7] Barbosa, HJC; Lemonge, ACC; Iba, H (ed.), An adaptive penalty method for genetic algorithms in constrained optimization problems, 34, (2008), Austria
[8] Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999)
[9] Birgin, E.G., Floudas, C.A., Martínez, J.M.: Global minimization using an Augmented Lagrangian method with variable lower-level constraints. Technical report MCDO121206, 22 Jan 2007 · Zbl 1180.65081
[10] Birgin, EG; Floudas, CA; Martínez, JM, Global minimization using an augmented Lagrangian method with variable lower-level constraints, Math. Program. Ser. A, 125, 139-162, (2010) · Zbl 1198.90322
[11] Birgin, EG; Martínez, JM, Augmented Lagrangian method with nonmonotone penalty parameters for constrained optimization, Comput. Optim. Appl., 51, 941-965, (2012) · Zbl 1244.90216
[12] Chootinan, P; Chen, A, Constrained handling in genetic algorithms using a gradient-based repair method, Comput. Oper. Res., 33, 2263-2281, (2006) · Zbl 1086.90058
[13] Civicioglu, P., Besdok, E.: A conceptual comparison of the Cuckoo-search, particle swarm optimization, differential evolution and artificial bee colony algorithms. Artif. Intell. Rev. 39(4), 315-346 (2013) · Zbl 1134.90542
[14] Coello Coello, CA, Theoretical and numerical constraint-handling techniques used with evolutionary algorithms, Comput. Methods Appl. Mech. Eng., 191, 1245-1287, (2002) · Zbl 1026.74056
[15] Costa, L; Espírito Santo, IACP; Fernandes, EMGP, A hybrid genetic pattern search augmented Lagrangian method for constrained global optimization, Appl. Math. Comput., 218, 9415-9426, (2012) · Zbl 1245.90087
[16] Costa, MFP; Fernandes, EMGP, Assessing the potential of interior point barrier filter line search methods: nonmonotone versus monotone approach, Optimization, 60, 1251-1268, (2011) · Zbl 1231.90342
[17] Deb, K; Srivastava, S, A genetic algorithm based augmented Lagrangian method for constrained optimization, Comput. Optim. Appl., 53, 869-902, (2012) · Zbl 1264.90159
[18] Dennis, JE; Price, CJ; Coope, ID, Direct search methods for nonlinear constrained optimization using filters and frames, Optim. Eng., 5, 123-144, (2004) · Zbl 1085.90054
[19] Pillo, G; Lucidi, S; Rinaldi, F, An approach to constrained global optimization based on exact penalty functions, J. Glob. Optim., 54, 251-260, (2012) · Zbl 1259.90099
[20] Durrett, R.: Probability: Theory and Examples, 4th edn. Cambridge University Press, Cambridge (2010) · Zbl 1202.60001
[21] Fletcher, R; Leyffer, S, Nonlinear programming without a penalty function, Math. Program., 91, 239-269, (2002) · Zbl 1049.90088
[22] Fletcher, R; Leyffer, S; Toint, PhL, A brief history of filter methods, SIAG/Optim. Views News, 18, 2-12, (2007)
[23] Gould, NIM; Leyffer, S; Toint, PhL, A multidimensional filter algorithm for nonlinear equations and nonlinear least squares, SIAM J. Optim., 15, 17-38, (2004) · Zbl 1075.65075
[24] Gould, NIM; Toint, PhL; Hager, WW (ed.); Huang, S-J (ed.); Pardalos, PM (ed.); Prokopyev, OA (ed.), Global convergence of a non-monotone trust-region filter algorithm for nonlinear programming, (2006), Berlin · Zbl 1130.90399
[25] Gómez, W; Remírez, H, A filter algorithm for nonlinear semidefinite programming, Comput. Appl. Math., 29, 297-328, (2010) · Zbl 1247.90248
[26] Gonzaga, CC; Castillo, RA, A nonlinear programming algorithm based on non-coercive penalty functions, Math. Program. Ser. A, 96, 87-101, (2003) · Zbl 1023.90061
[27] Greenwood, GW; Shu, QJ, Convergence in evolutionary programs with self-adaptation, Evol. Comput., 9, 147-157, (2001)
[28] He, Q; Wang, L, A hybrid particle swarm optimization with a feasibility-based rule for constrained optimization, Appl. Math. Comput., 186, 1407-1422, (2007) · Zbl 1117.65088
[29] Hedar, A.-R., Fahim, A.: Filter-based genetic algorithm for mixed variable programming. Numer. Algebra Control Optim. 1(1), 99-116 (2011) · Zbl 1219.90107
[30] Hedar, A-R; Fukushima, M, Derivative-free filter simulated annealing method for constrained continuous global optimization, J. Glob. Optim., 35, 521-549, (2006) · Zbl 1133.90421
[31] Hendrix, E.M.T., G.-Tóth, B.: Introduction to Nonlinear and Global Optimization, Optimization and its Applications. Vol. 37, Springer, Berlin (2010) · Zbl 1133.90421
[32] Jansen, PW; Perez, RE, Constrained structural design optimization via a parallel augmented Lagrangian particle swarm optimization approach, Comput. Struct., 89, 1352-1366, (2011)
[33] Jiang, M., Wang, Y., Pfletschinger, S., Lagunas, M.A., Yuan, D.: In: Huang, D.-S., et al. (eds.) ptimal multiuser detection with artificial fish swarm algorithm, CCIS 2, ICIC 2007, pp. 1084-1093. Springer, Berlin (2007) · Zbl 1011.65030
[34] Jin, Z., Wang, Y.: An improved line search filter method for the system of nonlinear equations. J. Appl. Math. ID 273141, 15pp. (2012) · Zbl 1268.65074
[35] Karas, EW; Gonzaga, CC; Ribeiro, AA, Local convergence of filter methods for equality constrained non-linear programming, Optimization, 59, 1153-1171, (2010) · Zbl 1221.49058
[36] Karas, E; Ribeiro, A; Sagastizábal, C; Solodov, M, A bundle-filter method for nonsmooth convex constrained optimization, Math. Program. Ser. B, 116, 297-320, (2009) · Zbl 1165.90024
[37] Karr, A.F.: Probability, Springer Texts in Statistics. Springer, New York (1993)
[38] Lewis, RM; Torczon, V, A globally convergent augmented Lagrangian pattern search algorithm for optimization with general constraints and simple bounds, SIAM J. Optim., 12, 1075-1089, (2002) · Zbl 1011.65030
[39] Liu, J-L; Lin, J-H, Evolutionary computation of unconstrained and constrained problems using a novel momentum-type particle swarm optimization, Eng. Optim., 39, 287-305, (2007)
[40] Luo, H; Sun, X; Wu, H, Convergence properties of augmented Lagrangian methods for constrained global optimization, Optim. Methods Softw., 23, 763-778, (2008) · Zbl 1154.90575
[41] Mahdavi, M; Fesanghary, M; Damangir, E, An improved search algorithm for solving optimization problems, Appl. Math. Comput., 188, 1567-1579, (2007) · Zbl 1119.65053
[42] Neshat, M., Sepidnam, G., Sargolzaei, M., Toosi, A.N.: Artificial fish swarm algorithm: a survey of the state-of-the-art, hybridization, combinatorial and indicative applications. Artif. Intell. Rev. (2012). doi:10.1007/s10462-012-9342-2
[43] Nie, P-Y; Fan, J-y, A derivative-free filter method for solving nonlinear complementarity problems, Appl. Math. Comput., 161, 787-797, (2005) · Zbl 1122.90080
[44] Nie, P-Y; Lai, M-Y; Zhu, S-J; Zhang, PA, A line search filter approach for the system of nonlinear equations, Comput. Math. Appl., 55, 2134-2141, (2008) · Zbl 1144.90491
[45] Pereira, AI; Costa, MFP; Fernandes, EMGP, Interior point filter method for semi-infinite programming problems, Optimization, 60, 1309-1338, (2011) · Zbl 1231.90347
[46] Petalas, YG; Parsopoulos, KE; Vrahatis, MN, Memetic particle swarm optimization, Ann. Oper. Res., 156, 99-127, (2007) · Zbl 1145.90108
[47] Ribeiro, AA; Karas, EW; Gonzaga, CC, Global convergence of filter methods for nonlinear programming, SIAM j. Optim., 19, 1231-1249, (2008) · Zbl 1169.49034
[48] Rocha, AMAC; Fernandes, EMGP, Numerical study of augmented Lagrangian algorithms for constrained global optimization, Optimization, 60, 1359-1378, (2011) · Zbl 1231.90348
[49] Rocha, A.M.A.C., Costa, M.F.P., Fernandes, E.M.G.P.: An artificial fish swarm filter-based method for constrained global optimization. In: Murgante, B., Gervasi, O., Misra, S., Nedjah, N., Rocha, A.M.A.C., Taniar, D., Apduhan, B.O. (eds.) Lecture Notes in Computer Science, ICCSA 2012 Part III, vol. 7335, pp. 57-71 (2012)
[50] Rocha, A.M.A.C., Fernandes, E.M.G.P., Martins, T.F.M.C.: Novel fish swarm heuristics for bound constrained global optimzation problems. In: Murgante, B., Gervasi, O., Iglesias, A., Taniar, D., Apduhan, B. (eds.) Lecture Notes in Computer Science, ICCSA 2011 Part III, vol. 6784, pp. 185-199 (2011) · Zbl 1258.90071
[51] Rocha, AMAC; Martins, TFMC; Fernandes, EMGP, An augmented Lagrangian fish swarm based method for global optimization, J. Comput. Appl. Math., 235, 4611-4620, (2011) · Zbl 1232.65093
[52] Scholz, D.: Geometric branch-and-bound methods for constrained global optimization problems. J. Glob. Optim. 57(3), 771-782 (2013) · Zbl 1286.90118
[53] Sedlaczek, K; Eberhard, P, Augmented Lagrangian particle swarm optimization in mechanism design, J. Syst. Des. Dyn., 1, 410-421, (2007)
[54] Shen, C; Leyffer, S; Fletcher, R, A nonmonotone filter method for nonlinear optimization, Comput. Optim. Appl., 52, 583-607, (2012) · Zbl 1259.90140
[55] Silva, EK; Barbosa, HJC; Lemonge, ACC, An adaptive constraint handling technique for differential evolution with dynamic use of variants in engineering optimization, Optim. Eng., 12, 31-54, (2011) · Zbl 1272.90124
[56] Silva, R., Ulbrich, M., Ulbrich, S., Vicente, L.N.: A globally convergent primal-dual interior-point filter method for nonlinear programming: New filter optimality measures and computational results. Technical report 08-49, Department of Mathematics, University of Coimbra (2009) · Zbl 1070.90110
[57] Tahk, M-J; Woo, H-W; Park, M-S, A hybrid optimization method of evolutionary and gradient search, Eng. Optim., 39, 87-104, (2007)
[58] Tsoulos, IG, Solving constrained optimization problems using a novel genetic algorithm, Appl. Math. Comput., 208, 273-283, (2009) · Zbl 1159.65063
[59] Wächter, A; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57, (2006) · Zbl 1134.90542
[60] Wang, H., Pu, D.: A nonmonotone filter trust region method for the system of nonlinear equations. Appl. Math. Mod. 37(1-2), 498-506 (2013). · Zbl 1349.90843
[61] Wang, X., Gao, N., Cai, S., Huang, M.: In: Min, G., et al. (eds.) An artificial fish swarm algorithm based and ABC supported QoS unicast routing scheme in NGI. In: Lecture Notes in Computer Science, ISPA, pp. 205-214. ISPA, Pakistan (2006) · Zbl 1205.90270
[62] Wu, T; Sun, L, A filter-based pattern search method for unconstrained optimization, Numer. Math., 15, 209-216, (2006) · Zbl 1132.65058
[63] Yu, K; Pu, D, A nonmonotone filter trust region method for nonlinear constrained optimization, J. Comput. Appl. Math., 223, 230-239, (2009) · Zbl 1180.65081
[64] Zahara, E; Hu, C-H, Solving constrained optimization problems with hybrid particle swarm optimization, Eng. Optim., 40, 1031-1049, (2008)
[65] Zhao, Q; Guo, N, A nonmonotone filter method for minimax problems, Appl. Math., 2, 1372-1377, (2011) · Zbl 1234.47007
[66] Zhou, YY; Yang, XQ, Augmented Lagrangian functions for constrained optimization problems, J. Glob. Optim., 52, 95-108, (2012) · Zbl 1258.90071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.