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页未读，继续阅读
weixin_38566318
- 粉丝: 7
- 资源: 972
我的内容管理
展开
最新资源
- 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显示实例及精度校准
- 反垃圾邮件技术：现状与前景
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
