American Institute of Mathematical Sciences

Advanced
2015, 5(2): 151-168. doi: 10.3934/naco.2015.5.151

Speeding up a memetic algorithm for the max-bisection problem

Wenxing Zhu 1, , Yanpo Liu 1, and  Geng Lin 2,

1. 

Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou 350108, China, China
2. 

Department of Mathematics, Minjiang University, Fuzhou, 350108, China

Received  September 2014 Revised  May 2015 Published  June 2015

Max-bisection of a weighted graph $G = (V, E)$ is to partition the vertex set $V$ into two subsets that have equal cardinality, such that the sum of the weights of the edges connecting vertices in different subsets is maximized. It is an NP-complete problem. Various heuristics have been proposed for solving the max-bisection problem and some of them get very good quality solutions, but are time consuming. In this paper, we propose several techniques to speeding up Lin and Zhu's memetic algorithm for this problem. It consists of a crossover operator with a greedy strategy, a fast modified Kernighan-Lin local search, and a new population updating function. Experiments are performed on 71 well-known G-set benchmark instances. Results show that the memetic algorithm is much faster than Wu and Hao's memetic algorithm, which can get best solutions up to now, on middle-scale and large-scale instances. Specifically, some current best known solutions of the test instances are improved.
Keywords: local search., memetic algorithm, Max-bisection, crossover.
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C3.
Citation: Wenxing Zhu, Yanpo Liu, Geng Lin. Speeding up a memetic algorithm for the max-bisection problem. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 151-168. doi: 10.3934/naco.2015.5.151
References:
[1]

C. Ashcraft and J. W. H. Liu, Using domain decomposition to find graph bisectors, BIT Numerical Mathematics, 37 (1997), 506-534. doi: 10.1007/BF02510238.

[2]

P. Austrin, S. Benabbas and K. Georgiou, Better balance by being biased: a 0.8776-approximation for max bisection, in Proceedings of SODA, (2013), 277-294. Full version available as arXiv eprint 1205.0458v2.

[3]

F. Barahona, M. Grötschel, M. Jünger and G. Reinelt, An application of combinatorial optimization to statistical physics and circuit layout design, Operations Research, 36 (1988), 493-513.

[4]

R. Battiti and A. Bertossi, Differential greedy for the 0-1 equicut problem, in Proceeding of the DIMACS Workshop on Network Design: Connectivity and Facilities Location (eds. D. Z. Du and P. M. Pardalos), 1997.

[5]

L. Brunetta, M. Conforti and G. Rinaldi, A branch-and-cut algorithm for the equicut problem, Mathematical Programming, 78 (1997), 243-263. doi: 10.1016/S0025-5610(97)00017-8.

[6]

K. C. Chang and D. H-C. Du, Efficient algorithms for layer assignment problems, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6 (1987), 67-78.

[7]

P. Chardaire, M. Barake and G. P. McKeown, A PROBE-based heuristic for graph partitioning, IEEE Transactions on Computers, 56 (2007), 1707-1720. doi: 10.1109/TC.2007.70760.

[8]

R. K. F. Chung, Spectral Graph Theory, 92, AMS Bookstore, 1997.

[9]

C. Dang, L. He and I. K. Hui, A deterministic annealing algorithm for approximating a solution of the max-bisection problem, Neural Networks, 15 (2002), 441-458.

[10]

A. Duarte, F. Fernández, Á. Sánchez and A. Sanz, A hierarchical social metaheuristic for the max-cut problem, Lecture Notes in computer Science, 3004 (2004), 84-94.

[11]

U. Feige, M. Karpinski and M. Langberg, A note on approximating max-bisection on regular graphs, Information Processing Letters, 79 (2001), 181-188. doi: 10.1016/S0020-0190(00)00189-7.

[12]

C. M. Fiduccia and R. M. Mattheyses, A linear time heuristic for improving network partitions, in Proceedings of the 19th Design Automation Conference, (1982), 175-181.

[13]

A. Frieze and M. Jerrum, Improved approximation algorithm for max k-cut and max-bisection, Algorithmica, 18 (1997), 67-81. doi: 10.1007/BF02523688.

[14]

M. X. Goemans and D. P. Williamson, Improved approximation algorithms for Max-Cut and satisfiability problems using semidefinite programming, Journal of the ACM, 42 (1995), 1115-1145. doi: 10.1145/227683.227684.

[15]

E. Halperin and U. Zwick, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems, Random Structures and Algorithms, 20 (2002), 382-402. doi: 10.1002/rsa.10035.

[16]

J. Hastad, Some optimal inapproachability results, in Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, ACM, New York, (1997), 1-10.

[17]

C. Helmberg and F. Rendl, A spectral bundle method for semidefinite programming, SIAM Journal on Optimization, 10 (2000), 673-696. doi: 10.1137/S1052623497328987.

[18]

B. Hendrickson and R. Leland, An improved spectral graph partitioning algorithm for mapping parallel computations, SIAM Journal on Scientific Computing, 16 (1995), 452-469. doi: 10.1137/0916028.

[19]

J. H. Holland, Adaptation in Natural Artificial System, The University of Michigan Press (Second edition; MIT press), 1992.

[20]

K. Jansen, M. Karpinski, A. Lingas and E. Seidel, Polynomial time approximation schemes for Max-Bisection on planar and geometric graphs, SIAM Journal on Computing, 35 (2005), 110-119. doi: 10.1137/S009753970139567X.

[21]

R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations (eds. R. E. Miller and J. W. Thatcher), Plenum Press, (1972), 85-103.

[22]

M. Karpinski, M. Kowaluk and A. Lingas, Approximation algorithms for MAX-BISECTION on low degree regular graphs, Fundamenta Informaticae, 62 (2004), 369-375.

[23]

B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs, The Bell System Technical Journal, 49 (1970), 291-307.

[24]

S. Khot, G. Kindler, E. Mossel and R. O'Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs, SIAM Journal on Computing, 37 (2007), 319-357. doi: 10.1137/S0097539705447372.

[25]

D. E. Knuth, Seminumerical Algorithms, The Art of Computer Programming, Vol. 2, Addison-Wesley, Reading, MA, 1997.

[26]

K. Krishnan and J. Mitchell, A semidefinite programming based polyhedral cut and price approach for the Max-Cut problem, Computational Optimization and Applications, 33 (2006), 51-71. doi: 10.1007/s10589-005-5958-3.

[27]

R. B. Lin and S. Y. Chen, Conjugate conflict continuation graphs for multilayer constrained via minimization, Information Sciences, 177 (2007), 2436-2447. doi: 10.1016/j.ins.2007.01.013.

[28]

G. Lin and W. Zhu, An efficient memetic algorithm for solving the Max-Bisection problem, IEEE Transactions on Computers, 63 (2014), 1365-1376. doi: 10.1109/TC.2013.7.

[29]

A. F. Ling, C. X. Xu and L. Tang, A modified VNS metaheuristic for max-bisection problems, Journal of Computational and Applied Mathematics, 220 (2008), 413-421. doi: 10.1016/j.cam.2007.08.018.

[30]

R. Marti, A. Duarte and M. Laguna, Advanced scatter search for the max-cut problem, INFORMS Journal on Computing, 21 (2009), 26-38. doi: 10.1287/ijoc.1080.0275.

[31]

P. Moscato and C. Cotta, A gentle introduction to memetic algorithms, in Handbook of Metaheuristics (eds. F. Glover and G. A. Kochenberger), Kluwer, Norwell, Massachusetts, USA, 2003. doi: 10.1007/0-306-48056-5_5.

[32]

K. G. Murty and S. N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Mathematical Programming, 39 (1987), 117-129. doi: 10.1007/BF02592948.

[33]

F. Neri, C. Cotta and P. Moscato, Handbook of Memetic Algorithms, Studies in Computational Intelligence, 379, Springer, 2011. doi: 10.1007/978-3-642-23247-3.

[34]

G. Palubeckis and V. Krivickiene, Application of multistart tabu search to the Max Cut problem, Information Technology and Control, 2 (2004), 29-35.

[35]

P. Raghavendra and N. Tan, Approximating CSPs with global cardinality constraints using SDP hierarchies, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2012, 373-387.

[36]

V. P. Shylo and O. V. Shylo, Solving the max-cut problem by the global equilibrium search, Cybernetics and Systems Analysis, 46 (2010), 744-754.

[37]

K. Sörensen and M. Sevaux, MA|PM: memetic algorithms with population management, Computers and Operations Research, 33 (2006), 1214-1225.

[38]

C. C. de Souza, R. Keunings, L. A. Wolsey and O. Zone, A new approach to minimizing the front width in finite element calculations, Computer Methods in Applied Mechanics and Engineering, 111 (1994), 323-334. doi: 10.1016/0045-7825(94)90137-6.

[39]

D. Spielman, Spectral Graph Theory, Lecture Notes, Yale University, 2009.

[40]

E. W. Weisstein, Laplacian Matrix, MathWorld-A Wolfram Web Resource, 1995.

[41]

Q. Wu and J. K. Hao, Memetic search for the max-bisection problem, Computers and Operations Research, 40 (2013), 166-179. doi: 10.1016/j.cor.2012.06.001.

[42]

F. Xu, X. Ma and B. Chen, A new Lagrangian net algorithm for solving max-bisection problems, Journal of Computational and Applied Mathematics, 235 (2011), 3718-3723. doi: 10.1016/j.cam.2011.01.015.

[43]

Y. Y. Ye, A 0.699-approximation algorithm for Max-Bisection, Mathematical Programming, 90 (2001), 101-111. doi: 10.1007/PL00011415.

show all references

References:
[1]

C. Ashcraft and J. W. H. Liu, Using domain decomposition to find graph bisectors, BIT Numerical Mathematics, 37 (1997), 506-534. doi: 10.1007/BF02510238.

[2]

P. Austrin, S. Benabbas and K. Georgiou, Better balance by being biased: a 0.8776-approximation for max bisection, in Proceedings of SODA, (2013), 277-294. Full version available as arXiv eprint 1205.0458v2.

[3]

F. Barahona, M. Grötschel, M. Jünger and G. Reinelt, An application of combinatorial optimization to statistical physics and circuit layout design, Operations Research, 36 (1988), 493-513.

[4]

R. Battiti and A. Bertossi, Differential greedy for the 0-1 equicut problem, in Proceeding of the DIMACS Workshop on Network Design: Connectivity and Facilities Location (eds. D. Z. Du and P. M. Pardalos), 1997.

[5]

L. Brunetta, M. Conforti and G. Rinaldi, A branch-and-cut algorithm for the equicut problem, Mathematical Programming, 78 (1997), 243-263. doi: 10.1016/S0025-5610(97)00017-8.

[6]

K. C. Chang and D. H-C. Du, Efficient algorithms for layer assignment problems, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6 (1987), 67-78.

[7]

P. Chardaire, M. Barake and G. P. McKeown, A PROBE-based heuristic for graph partitioning, IEEE Transactions on Computers, 56 (2007), 1707-1720. doi: 10.1109/TC.2007.70760.

[8]

R. K. F. Chung, Spectral Graph Theory, 92, AMS Bookstore, 1997.

[9]

C. Dang, L. He and I. K. Hui, A deterministic annealing algorithm for approximating a solution of the max-bisection problem, Neural Networks, 15 (2002), 441-458.

[10]

A. Duarte, F. Fernández, Á. Sánchez and A. Sanz, A hierarchical social metaheuristic for the max-cut problem, Lecture Notes in computer Science, 3004 (2004), 84-94.

[11]

U. Feige, M. Karpinski and M. Langberg, A note on approximating max-bisection on regular graphs, Information Processing Letters, 79 (2001), 181-188. doi: 10.1016/S0020-0190(00)00189-7.

[12]

C. M. Fiduccia and R. M. Mattheyses, A linear time heuristic for improving network partitions, in Proceedings of the 19th Design Automation Conference, (1982), 175-181.

[13]

A. Frieze and M. Jerrum, Improved approximation algorithm for max k-cut and max-bisection, Algorithmica, 18 (1997), 67-81. doi: 10.1007/BF02523688.

[14]

M. X. Goemans and D. P. Williamson, Improved approximation algorithms for Max-Cut and satisfiability problems using semidefinite programming, Journal of the ACM, 42 (1995), 1115-1145. doi: 10.1145/227683.227684.

[15]

E. Halperin and U. Zwick, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems, Random Structures and Algorithms, 20 (2002), 382-402. doi: 10.1002/rsa.10035.

[16]

J. Hastad, Some optimal inapproachability results, in Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, ACM, New York, (1997), 1-10.

[17]

C. Helmberg and F. Rendl, A spectral bundle method for semidefinite programming, SIAM Journal on Optimization, 10 (2000), 673-696. doi: 10.1137/S1052623497328987.

[18]

B. Hendrickson and R. Leland, An improved spectral graph partitioning algorithm for mapping parallel computations, SIAM Journal on Scientific Computing, 16 (1995), 452-469. doi: 10.1137/0916028.

[19]

J. H. Holland, Adaptation in Natural Artificial System, The University of Michigan Press (Second edition; MIT press), 1992.

[20]

K. Jansen, M. Karpinski, A. Lingas and E. Seidel, Polynomial time approximation schemes for Max-Bisection on planar and geometric graphs, SIAM Journal on Computing, 35 (2005), 110-119. doi: 10.1137/S009753970139567X.

[21]

R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations (eds. R. E. Miller and J. W. Thatcher), Plenum Press, (1972), 85-103.

[22]

M. Karpinski, M. Kowaluk and A. Lingas, Approximation algorithms for MAX-BISECTION on low degree regular graphs, Fundamenta Informaticae, 62 (2004), 369-375.

[23]

B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs, The Bell System Technical Journal, 49 (1970), 291-307.

[24]

S. Khot, G. Kindler, E. Mossel and R. O'Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs, SIAM Journal on Computing, 37 (2007), 319-357. doi: 10.1137/S0097539705447372.

[25]

D. E. Knuth, Seminumerical Algorithms, The Art of Computer Programming, Vol. 2, Addison-Wesley, Reading, MA, 1997.

[26]

K. Krishnan and J. Mitchell, A semidefinite programming based polyhedral cut and price approach for the Max-Cut problem, Computational Optimization and Applications, 33 (2006), 51-71. doi: 10.1007/s10589-005-5958-3.

[27]

R. B. Lin and S. Y. Chen, Conjugate conflict continuation graphs for multilayer constrained via minimization, Information Sciences, 177 (2007), 2436-2447. doi: 10.1016/j.ins.2007.01.013.

[28]

G. Lin and W. Zhu, An efficient memetic algorithm for solving the Max-Bisection problem, IEEE Transactions on Computers, 63 (2014), 1365-1376. doi: 10.1109/TC.2013.7.

[29]

A. F. Ling, C. X. Xu and L. Tang, A modified VNS metaheuristic for max-bisection problems, Journal of Computational and Applied Mathematics, 220 (2008), 413-421. doi: 10.1016/j.cam.2007.08.018.

[30]

R. Marti, A. Duarte and M. Laguna, Advanced scatter search for the max-cut problem, INFORMS Journal on Computing, 21 (2009), 26-38. doi: 10.1287/ijoc.1080.0275.

[31]

P. Moscato and C. Cotta, A gentle introduction to memetic algorithms, in Handbook of Metaheuristics (eds. F. Glover and G. A. Kochenberger), Kluwer, Norwell, Massachusetts, USA, 2003. doi: 10.1007/0-306-48056-5_5.

[32]

K. G. Murty and S. N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Mathematical Programming, 39 (1987), 117-129. doi: 10.1007/BF02592948.

[33]

F. Neri, C. Cotta and P. Moscato, Handbook of Memetic Algorithms, Studies in Computational Intelligence, 379, Springer, 2011. doi: 10.1007/978-3-642-23247-3.

[34]

G. Palubeckis and V. Krivickiene, Application of multistart tabu search to the Max Cut problem, Information Technology and Control, 2 (2004), 29-35.

[35]

P. Raghavendra and N. Tan, Approximating CSPs with global cardinality constraints using SDP hierarchies, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2012, 373-387.

[36]

V. P. Shylo and O. V. Shylo, Solving the max-cut problem by the global equilibrium search, Cybernetics and Systems Analysis, 46 (2010), 744-754.

[37]

K. Sörensen and M. Sevaux, MA|PM: memetic algorithms with population management, Computers and Operations Research, 33 (2006), 1214-1225.

[38]

C. C. de Souza, R. Keunings, L. A. Wolsey and O. Zone, A new approach to minimizing the front width in finite element calculations, Computer Methods in Applied Mechanics and Engineering, 111 (1994), 323-334. doi: 10.1016/0045-7825(94)90137-6.

[39]

D. Spielman, Spectral Graph Theory, Lecture Notes, Yale University, 2009.

[40]

E. W. Weisstein, Laplacian Matrix, MathWorld-A Wolfram Web Resource, 1995.

[41]

Q. Wu and J. K. Hao, Memetic search for the max-bisection problem, Computers and Operations Research, 40 (2013), 166-179. doi: 10.1016/j.cor.2012.06.001.

[42]

F. Xu, X. Ma and B. Chen, A new Lagrangian net algorithm for solving max-bisection problems, Journal of Computational and Applied Mathematics, 235 (2011), 3718-3723. doi: 10.1016/j.cam.2011.01.015.

[43]

Y. Y. Ye, A 0.699-approximation algorithm for Max-Bisection, Mathematical Programming, 90 (2001), 101-111. doi: 10.1007/PL00011415.

[1]

Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial and Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041
[2]

Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $ k $-facility location problem with linear penalties. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056
[3]

Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030
[4]

Dieudonné Nijimbere, Songzheng Zhao, Xunhao Gu, Moses Olabhele Esangbedo, Nyiribakwe Dominique. Tabu search guided by reinforcement learning for the max-mean dispersion problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3223-3246. doi: 10.3934/jimo.2020115
[5]

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial and Management Optimization, 2020, 16 (1) : 103-115. doi: 10.3934/jimo.2018142
[6]

Baolan Yuan, Wanjun Zhang, Yubo Yuan. A Max-Min clustering method for $k$-means algorithm of data clustering. Journal of Industrial and Management Optimization, 2012, 8 (3) : 565-575. doi: 10.3934/jimo.2012.8.565
[7]

Erik Carlsson, John Gunnar Carlsson, Shannon Sweitzer. Applying topological data analysis to local search problems. Foundations of Data Science, 2022  doi: 10.3934/fods.2022006
[8]

Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control and Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193
[9]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control and Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015
[10]

Mohamed A. Tawhid, Ahmed F. Ali. An effective hybrid firefly algorithm with the cuckoo search for engineering optimization problems. Mathematical Foundations of Computing, 2018, 1 (4) : 349-368. doi: 10.3934/mfc.2018017
[11]

Ming-Jong Yao, Tien-Cheng Hsu. An efficient search algorithm for obtaining the optimal replenishment strategies in multi-stage just-in-time supply chain systems. Journal of Industrial and Management Optimization, 2009, 5 (1) : 11-32. doi: 10.3934/jimo.2009.5.11
[12]

Abdel-Rahman Hedar, Ahmed Fouad Ali, Taysir Hassan Abdel-Hamid. Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191
[13]

Zheng Chang, Haoxun Chen, Farouk Yalaoui, Bo Dai. Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1771-1793. doi: 10.3934/jimo.2020045
[14]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial and Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703
[15]

Leong-Kwan Li, Sally Shao, K. F. Cedric Yiu. Nonlinear dynamical system modeling via recurrent neural networks and a weighted state space search algorithm. Journal of Industrial and Management Optimization, 2011, 7 (2) : 385-400. doi: 10.3934/jimo.2011.7.385
[16]

Sen Zhang, Guo Zhou, Yongquan Zhou, Qifang Luo. Quantum-inspired satin bowerbird algorithm with Bloch spherical search for constrained structural optimization. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3509-3523. doi: 10.3934/jimo.2020130
[17]

Bin Feng, Lixin Wei, Ziyu Hu. An adaptive large neighborhood search algorithm for Vehicle Routing Problem with Multiple Time Windows constraints. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021197
[18]

Yunsai Chen, Zhao Yang, Liang Ma, Peng Li, Yongjie Pang, Xin Zhao, Wenyi Yang. Efficient extraction algorithm for local fuzzy features of dynamic images. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1311-1325. doi: 10.3934/dcdss.2019090
[19]

Tao Zhang, Yue-Jie Zhang, Qipeng P. Zheng, P. M. Pardalos. A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories based on the Make-To-Stock and Make-To-Order management architecture. Journal of Industrial and Management Optimization, 2011, 7 (1) : 31-51. doi: 10.3934/jimo.2011.7.31
[20]

Adrian Korban, Serap Sahinkaya, Deniz Ustun. New type I binary $[72, 36, 12]$ self-dual codes from $M_6(\mathbb{F}_2)G$ - Group matrix rings by a hybrid search technique based on a neighbourhood-virus optimisation algorithm. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022032

 Impact Factor: 

Tools

Metrics

  • PDF downloads (172)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy