An adaptive memetic algorithm for solving the set covering problem(自适应memetic算法求解集合覆盖问题)
集合覆盖问题是一个经典的NP困难的组合优化问题，有着广泛的应用背景.首先，采用动态罚函数法将集合覆盖问题等价转化为无约束的0-1规划问题.然后，基于集合覆盖问题的结构特征，设计了初始种群构造方法、局部搜索方法、交叉算子、动态变异算子和路径重连策略，提出了一个高效求解该0-1规划问题的自适应memetic算法.该算法有效平衡了集中搜索和多样化搜索.通过45个标准例子测试该算法，并将其结果与现有遗传算法进行了比较，表明该算法能够在可接受的时间内找到高质量的解，能够有效求解大规模集合覆盖问题....
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Zhejiang University Press
2016-03-01
|
| Series: | Zhejiang Daxue xuebao. Lixue ban |
| Subjects: | |
| Online Access: | https://doi.org/10.3785/j.issn.1008-9497.2016.02.008 |
| _version_ | 1797235890931630080 |
|---|---|
| author | LINGeng(林耿) GUANJian(关健) |
| author_facet | LINGeng(林耿) GUANJian(关健) |
| author_sort | LINGeng(林耿) |
| collection | DOAJ |
| description | 集合覆盖问题是一个经典的NP困难的组合优化问题，有着广泛的应用背景.首先，采用动态罚函数法将集合覆盖问题等价转化为无约束的0-1规划问题.然后，基于集合覆盖问题的结构特征，设计了初始种群构造方法、局部搜索方法、交叉算子、动态变异算子和路径重连策略，提出了一个高效求解该0-1规划问题的自适应memetic算法.该算法有效平衡了集中搜索和多样化搜索.通过45个标准例子测试该算法，并将其结果与现有遗传算法进行了比较，表明该算法能够在可接受的时间内找到高质量的解，能够有效求解大规模集合覆盖问题. |
| first_indexed | 2024-04-24T16:55:09Z |
| format | Article |
| id | doaj.art-289003b4c16943fc99e6ebce6d35bdc1 |
| institution | Directory Open Access Journal |
| issn | 1008-9497 |
| language | zho |
| last_indexed | 2024-04-24T16:55:09Z |
| publishDate | 2016-03-01 |
| publisher | Zhejiang University Press |
| record_format | Article |
| series | Zhejiang Daxue xuebao. Lixue ban |
| spelling | doaj.art-289003b4c16943fc99e6ebce6d35bdc12024-03-29T01:58:35ZzhoZhejiang University PressZhejiang Daxue xuebao. Lixue ban1008-94972016-03-0143216817410.3785/j.issn.1008-9497.2016.02.008An adaptive memetic algorithm for solving the set covering problem(自适应memetic算法求解集合覆盖问题)LINGeng(林耿)0https://orcid.org/0000-0002-1643-6859GUANJian(关健)1 1.Department of Mathematics, Minjiang University, Fuzhou 350108, China( 1.闽江学院数学系，福建 福州 350108) 2.Modern Educational Technology Center, Minjiang University, Fuzhou 350108, China( 2.闽江学院现代教育技术中心，福建 福州 350108)集合覆盖问题是一个经典的NP困难的组合优化问题，有着广泛的应用背景.首先，采用动态罚函数法将集合覆盖问题等价转化为无约束的0-1规划问题.然后，基于集合覆盖问题的结构特征，设计了初始种群构造方法、局部搜索方法、交叉算子、动态变异算子和路径重连策略，提出了一个高效求解该0-1规划问题的自适应memetic算法.该算法有效平衡了集中搜索和多样化搜索.通过45个标准例子测试该算法，并将其结果与现有遗传算法进行了比较，表明该算法能够在可接受的时间内找到高质量的解，能够有效求解大规模集合覆盖问题.https://doi.org/10.3785/j.issn.1008-9497.2016.02.008集合覆盖问题memetic算法罚函数局部搜索路径重连 |
| spellingShingle | LINGeng(林耿) GUANJian(关健) An adaptive memetic algorithm for solving the set covering problem(自适应memetic算法求解集合覆盖问题) Zhejiang Daxue xuebao. Lixue ban 集合覆盖问题 memetic算法 罚函数 局部搜索 路径重连 |
| title | An adaptive memetic algorithm for solving the set covering problem(自适应memetic算法求解集合覆盖问题) |
| title_full | An adaptive memetic algorithm for solving the set covering problem(自适应memetic算法求解集合覆盖问题) |
| title_fullStr | An adaptive memetic algorithm for solving the set covering problem(自适应memetic算法求解集合覆盖问题) |
| title_full_unstemmed | An adaptive memetic algorithm for solving the set covering problem(自适应memetic算法求解集合覆盖问题) |
| title_short | An adaptive memetic algorithm for solving the set covering problem(自适应memetic算法求解集合覆盖问题) |
| title_sort | adaptive memetic algorithm for solving the set covering problem 自适应memetic算法求解集合覆盖问题 |
| topic | 集合覆盖问题 memetic算法 罚函数 局部搜索 路径重连 |
| url | https://doi.org/10.3785/j.issn.1008-9497.2016.02.008 |
| work_keys_str_mv | AT lingenglíngěng anadaptivememeticalgorithmforsolvingthesetcoveringproblemzìshìyīngmemeticsuànfǎqiújiějíhéfùgàiwèntí AT guanjianguānjiàn anadaptivememeticalgorithmforsolvingthesetcoveringproblemzìshìyīngmemeticsuànfǎqiújiějíhéfùgàiwèntí AT lingenglíngěng adaptivememeticalgorithmforsolvingthesetcoveringproblemzìshìyīngmemeticsuànfǎqiújiějíhéfùgàiwèntí AT guanjianguānjiàn adaptivememeticalgorithmforsolvingthesetcoveringproblemzìshìyīngmemeticsuànfǎqiújiějíhéfùgàiwèntí |