没有合适的资源?快使用搜索试试~ 我知道了~
首页基于局部搜索与重启的进化算法:求解三元乘积特性三元组
基于局部搜索与重启的进化算法:求解三元乘积特性三元组
0 下载量 37 浏览量
更新于2024-07-15
收藏 2.38MB PDF 举报
本文主要探讨了"基于本地搜索的重新启动进化算法在寻找三元乘积特性三元组中的应用",发表于2018年的《应用智能》(Applied Intelligence)期刊,卷48,页码2894-2911。文章的DOI为10.1007/s10489-017-1118-6。该研究由Yi Xiang、Yuren Zhou和Zefeng Chen共同完成,并于2018年1月13日在线发布。矩阵乘法的指数界限ω问题一直以来是计算复杂性理论中的一个重要挑战,Cohn和Umans在2003年引入了群论方法来加速矩阵乘法,其中关键任务是找到三个给定群的子集,满足所谓的三元乘积性质,使得它们的大小乘积尽可能大。 传统上,为解决这一难题,已经提出过精确或随机化的启发式算法,但在群的阶数较大时,这些算法往往效率低下或者耗时较长。本文作者针对这一挑战,提出了利用进化算法来求解这个问题。具体而言,他们设计了一种算法,结合了局部搜索策略来增强算法的优化能力,确保在已知解区域进行深入挖掘,提高搜索效率;同时,通过重新启动策略,激发了算法在探索新解空间的能力,防止陷入局部最优。 这种混合方法旨在平衡算法的探索与利用,使算法能够在大规模非阿贝尔群上实现更有效的性能。作者对大量非阿贝尔群进行了实验测试,结果表明,他们的算法在解决三元乘积特性三元组问题上表现出了显著的优势,可能为矩阵乘法的复杂性分析提供了新的解决方案和启发。因此,这篇文章对于理解群论方法在数值计算中的实际应用,以及优化搜索算法在处理复杂优化问题上的作用具有重要意义。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/15630082/bg4.jpg)
A local search based restart evolutionary algorithm for finding triple product property triples 2897
a maximal TPP triple (S,T,U) for a given group. The
following collected results on TPP triples are useful in find
a maximal TPP triple.
Lemma 1 ([4]) If (S,T,U)is a TPP triple of a given group
G,then(dSa,dTb,dUc) is also a TPP triple of G,where
a, b,c and d are four arbitrary elements of G; and dSa,
dT b and dUc denote the sets {dsa|s ∈ S}, {dtb|t ∈ T } and
{duc|u ∈ U }, respectively.
Lemma 1 tells us that we can search for only basic TPP
triples, because any TPP triple can be transformed to a basic
one by this lemma.
Lemma 2 ([9]) It is sufficient to search TPP triples with
2 ≤|S|≤|G|−1, 2 ≤|T |≤|G|−1 and 2 ≤|U |≤|G|−1.
Lemma 3 ([17]) It is sufficient to search TPP triples with
|S|(|T |+|U|−1) ≤|G|, |T |(|S|+|U|−1) ≤|G| and
|U|(|S|+|T |−1) ≤|G|.
Lemma
4 ([9]) For a given group G, its three subsets S,
T and U form a TPP triple (S,T,U) if and only if each
permutation (X,Y,Z)of S, T and U meets all the following
properties.
1 ∈ X ∩ Y ∩ Z, (2)
Q(X) ∩ Q(Y ) = 1, (3)
Q(X) ∩ Q(Y )Q(Z) = 1. (4)
These lemmas are very useful for the EA to find maximal
TPP triples. The next section will show the readers how to
use them in our proposed LS-R-EA algorithm.
3 The proposed LS-R-EA
In this section, we describe in detail the proposed LS-R-EA
for finding TPP triples useful for the fast matrix multi-
plication problem. We first depict the encoding/decoding
schemes, and then we present the general framework of the
new algorithm. Finally, we give details of the main algorith-
mic components, including the population initialization, the
mutation operator, the local search technique and the restart
strategy.
3.1 Encoding and decoding schemes
In the group-theoretic approach to fast matrix multiplica-
tion, one challenging problem is to find three subsets S, T
and U of a group G ={1 = g
0
,g
1
,...,g
|G|−1
} satisfying
the TPP such that the product of their sizes is as large as
possible. To deal with the above problem by EAs, a solution
to the problem should be first encoded to a chromosome so
as to be handled by genetic operators.
According to Lemma 1, we can only concentrate on basic
TPP triples. Thus, the identity element g
0
(also denoted by
1) should be always included in the three subsets S,T and
U.Since1∈ S,wethenhaveS ⊆ Q(S) as for any s ∈ S,
we can get s = s1 = s1
−1
∈ Q(S). Along with (3), we have
Q(T ) ∩ S = Q(U) ∩ S = 1. (5)
Further, we have S ∩ T ={1}, S ∩ U ={1} and
T ∩ U ={1}. In other words, any element in G\{1} can not
appear simultaneously in any two of S, T and U if (S,T,U)
is a TPP triple. With this in mind, we only need to encode
elements from g
1
to g
|G|−1
by placing them in one of S, T
and U, or none of them. Therefore, a solution in this paper is
encoded by a vector with length |G|−1as{0, 1, 2, 3}
|G|−1
,
where 1, 2, 3 and 0 mean that the corresponding element
in G is included in S, T , U and none of them, respectively.
For example, let G ={1 = g
0
,g
1
,...,g
7
}, S ={g
0
,g
4
},
T ={g
0
,g
3
} and U ={g
0
,g
5
,g
7
}, then the triple (S,T,U)
can be encoded as (0, 0, 2, 1, 3, 0, 3).
Conversely, a chromosome can be easily decoded to
a triple accordingly. For example, if a representation is
(2, 0, 1, 3, 2, 0, 0), which means g
3
is included in S; g
1
and
g
5
are included in T ; g
4
is included in U ; g
2
, g
6
and g
7
are
not included in any set, then S ={g
0
,g
3
}, T ={g
0
,g
1
,g
5
}
and U ={g
0
,g
4
}.
One of the main advantages of the above encod-
ing/decoding schemas is that they are very straightforward
and can be easily handled by a computer program.
3.2 General framework of LS-R-EA
The general framework of LS-R-EA is shown in Algo-
rithm 1. Besides two common control parameters for EAs,
i.e., the population size (N) and the number of maximum
generations Gmax, two additional parameters should be
specified in LS-R-EA. One is the group under consideration
(G), and the other is the restart period R.SinceG speci-
fies which group to be considered, and is usually determined
by users, it is unnecessary to tune this parameter. However,
the optimal values for R should be found out according to
experimental studies which will be available in Section 4.4.
With the function Initialize() (line 2 in Algorithm 1),
LS-R-EA starts by initializing a population P with N
zero solutions, i.e., P =[x
1
, x
2
,...,x
N
],wherex
i
=
|G|−1
(
0, 0,...,0
)
,i = 1,...,N. This initialization implies that
the search of each individual in P starts from the basic
TPP triple (S,T,U) where S = T = U ={1}, i.e., the
triple realizing 1, 1, 1. Subsequently, the triple is extended
剩余17页未读,继续阅读
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
weixin_38566318
- 粉丝: 7
- 资源: 972
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- Hadoop生态系统与MapReduce详解
- MDS系列三相整流桥模块技术规格与特性
- MFC编程:指针与句柄获取全面解析
- LM06:多模4G高速数据模块,支持GSM至TD-LTE
- 使用Gradle与Nexus构建私有仓库
- JAVA编程规范指南:命名规则与文件样式
- EMC VNX5500 存储系统日常维护指南
- 大数据驱动的互联网用户体验深度管理策略
- 改进型Booth算法:32位浮点阵列乘法器的高速设计与算法比较
- H3CNE网络认证重点知识整理
- Linux环境下MongoDB的详细安装教程
- 压缩文法的等价变换与多余规则删除
- BRMS入门指南:JBOSS安装与基础操作详解
- Win7环境下Android开发环境配置全攻略
- SHT10 C语言程序与LCD1602显示实例及精度校准
- 反垃圾邮件技术:现状与前景
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)