Journal of Computer Science Applications and
Information Technology

Frank t-norms are parametric family of continuous Archimedean t-norms which are also strict when the parameter is nonnegative. Very often, this family of t-norms is also called the family of fundamental t-norms because of the role it plays in several applications. In this paper, we study a nonlinear optimization problem with a special system of Fuzzy Relational Equations (FRE) as its constraints. We firstly investigate the resolution of the feasible solutions set when it is defined with max-Frank composition and present some necessary and sufficient conditions for determining the feasibility and some procedures for simplifying the problem. Since the feasible solutions set of FREs is non-convex and the finding of all minimal solutions is an NP-hard problem, conventional nonlinear programming methods may involve high computation complexity. Based on the obtained theoretical properties of the problem, a genetic algorithm is used, which preserves the feasibility of new generated solutions and does not need to initially find the minimal solutions. Moreover, a method is presented to generate feasible max-Frank FREs as test problems for evaluating the performance of our algorithm. The presented method has been compared with some related works. The obtained results confirm the high performance of the current method in solving such nonlinear problems.

Keywords: Fuzzy relational equations; Nonlinear optimization; Genetic algorithm;

In this paper, we study the following nonlinear problem in which the constraints are formed as fuzzy relational equations defined by Frank t-norm:

where $I=\{1,2,\mathrm{...},m\},J=\{1,2,\mathrm{...},n\},A={(a_{ij})}_{m\times n},0\le a_{ij}\le 1\text{ (}\forall i\in I$ and $\forall j\in J),$ is a fuzzy matrix, $b={(b_i^{})}_{m\times 1},0\le b_i\le 1\text{ (}\forall i\in I),$ is an $m$ dimensional fuzzy vector, and "$\phi$ " is the max-Frank composition, that is, $\phi (x,y)=T_F^s(x,y)={\log }_s\left(1+\frac{(s^x-1)(s^y-1)}{s-1}\right)$ in which s >0 and s≠ 1.

If $a_i$ is the i’th row of matrix A, then problem (1) can be expressed as follows:

where the constraints mean: $$\phi (a_i,x)=\underset{j\in J}{\max }\{\phi (a_{ij},x_j)\}=\underset{j\in J}{\max }\{T_F^s(a_{ij},x_j)\}=\underset{j\in J}{\max }\left\{{\log }_s\left(1+\frac{(s^{a_{ij}}-1)(s^{x_j}-1)}{s-1}\right)\right\}=b_i,\forall i\in I$$

The above definition can be extended for $s=0,s=1$ and $s=\infty$ by taking limits. So, it is easy to verify that $T_F^0(x,y)=\min \{x,y\},T_F^1(x,y)=xy$ and $T_F^{\infty }(x,y)=\max \{x+y-1,0\},$ that is, Frank t-norm is converted to minimum, product and Lukasiewicz t-norm, respectively. Frank family of t-norms plays a central role in the investigation of the contraposition law for QL-implications [8].

The theory of fuzzy relational equations was firstly proposed by Sanchez, [52]. He introduced a FRE whit max-min composition and applied the model to medical diagnosis in Brouwerian logic. Nowadays, it is well-known that many issues associated with a body knowledge can be treated as FRE problems [44]. In addition to such applications, FRE theory has been applied in many fields including fuzzy control, discrete dynamic systems, prediction of fuzzy systems, fuzzy decision making, fuzzy pattern recognition, fuzzy clustering, image compression and reconstruction, and so on. Pedrycz, [45] categorized and extended two ways of the generalizations of FRE in terms of sets under discussion and various operations which are taken into account. Since then, many theoretical improvements have been investigated and many applications have been presented [2,3,5,11,24,28,32,37,38, 41,43,46,48,49,57,59,65].

The solvability and the finding of solutions set are the primary (and the most fundamental) subject concerning FRE problems. Many studies have reported fuzzy relational equations with max-min and max-product compositions. Both compositions are special cases of the max-triangular-norm (max-t-norm). Di Nola, et al. proved that the solution set of FRE defined by continuous max-t-norm composition is often a non-convex set that is completely determined by one maximum solution and a finite number of minimal solutions [6]. Over the last decades, the solvability of FRE defined with different max-t compositions has been investigated by many researches [36,47,50,51,53,55,56,60, 64,68].

Optimizing an objective function subjected to a system of fuzzy relational equations or inequalities (FRI) is one of the most interesting and on-going topics among the problems related to the FRE (or FRI) theory [1,9,19-27,25-27,33,34,39,54,61,66]. By far the most frequently studied aspect is the determination of a minimize of a linear objective function and the use of the maxmin composition [1,20]. So, it is an almost standard approach to translate this type of problem into a corresponding 0-1 integer linear programming problem, which is then solved using a branch and bound method [10,62]. The topic of the linear optimization problem was also investigated with max-product operation [19,26,40]. Moreover, some studies have determined a more general operator of linear optimization with replacement of max-min and max-product compositions with a max-t-norm composition, max-average composition or max-star composition [25,34,54,31,61,22,27].

Recently, many interesting generalizations of the linear and non-linear programming problems constrained by FRE or FRI have been introduced and developed based on composite operations and fuzzy relations used in the definition of the constraints, and some developments on the objective function of the problems [4,7,12,20,35,39,58,63,66]. For instance, the linear optimization of bipolar FRE was studied by some researchers where FRE was defined with max-min composition and max- Lukasiewicz composition [12,35,39]. Ghodousian and khorram, [21] focused on the algebraic structure of two fuzzy relational $A\phi x\le b^1$ and $D\phi x\ge b^2$ , and studied a mixed fuzzy system formed by the two preceding FRIs, where $\varphi$ is an operator with (closed) convex solutions. Yang, [67] studied the optimal solution of minimizing a linear objective function subject to fuzzy relational inequalities where the constraints defined as $a_{i1}\wedge x_1+a_{i2}\wedge x_2+\mathrm{...}+a_{in}\wedge x_n\ge b_i$ for $i=1,\mathrm{...},m$ and $a\wedge b=\min \{a,b\}.$ In [20], the authors introduced FRI-FC problem $\min \{c^{T}x:A\phi x\preccurlyeq b,x\in {[0,1]}^n\},$ where $\varphi$ is max-min composition and “$\preccurlyeq$ ” denotes the relaxed or fuzzy version of the ordinary inequality “$\preccurlyeq$ ”. Another interesting generalization of such optimization problems are related to objective function. Wu, et al. [63] represented an efficient method to optimize a linear fractional programming problem under FRE with max-Archimedean t-norm composition. Dempe and Ruziyeva, [4] generalized the fuzzy linear optimization problem by considering fuzzy coefficients. Dubey, et al. [7] studied linear programming problems involving interval uncertainty modeled using intuitionistic fuzzy set [7]. On the other hand, Lu and Fang considered the single non-linear objective function and solved it with FRE constraints and max-min operator [42]. They proposed a genetic algorithm for solving the problem. In [29], the authors used the same method for max-product operator. Also, Ghodousian, et al. [15,16,18] presented GA algorithms to solve the non-linear problem with FRE constraints defined by Lukasiewicz, Dubois –Prade and Sugeno-Weber operators.

Generally, there are three important difficulties related to FRE or FRI problems. Firstly, in order to completely determine FREs and FRIs, we must initially find all the minimal solutions, and the finding of all the minimal solutions is an NP-hard problem. Secondly, a feasible region formed as FRE or FRI is often a nonconvex set [21]. Finally, FREs and FRIs as feasible regions lead to optimization problems with highly non-linear constraints. Due to the above mentioned difficulties, although the analytical methods are efficient to find exact optimal solutions, they may also involve high computational complexity for high-dimensional problems (especially, if the simplification processes cannot considerably reduce the problem).

In this paper, we use the genetic algorithm proposed in [21] for solving problem (1), which keeps the search inside of the feasible region without finding any minimal solution and checking the feasibility of new generated solutions. Since the feasibility of problem (1) is essentially dependent on the t-norm (Frank t-norm) used in the definition of the constraints, a method is also presented to construct feasible test problems. More precisely, we construct a feasible problem by randomly generating a fuzzy matrix and a fuzzy vector according to some criteria resulted from the necessary and sufficient conditions. It is proved that the max-Frank fuzzy relational equations constructed by this method are not empty. Moreover, a comparison is made between the current method and the algorithms presented in [42] and [29].

The remainder of the paper is organized as follows. Section 2 takes a brief look at some basic results on the feasible solutions set of problem (1). In Section 3, the GA algorithm is briefly described. Finally, in Section 4 the experimental results are demonstrated and a conclusion is provided in Section 5.

This section describes the basic definitions and structural properties concerning problem (1) that are used throughout the paper. For the sake of simplicity, let $S_{T_F^s}(a_i,b_i)$ denote the feasible solutions set of i‘th equation, that is, $S_{T_F^s}(a_i,b_i)=\left\{x\in {[0,1]}^n:\underset{j=1}{\overset{n}{\max }}\left\{T_F^s(a_{ij},x_j)\right\}=b_i\right\}$. Also, let $S_{T_F^s}(A,b)$ denote the feasible solutions set of problem (1). Based on the foregoing notations, it is clear that $S_{T_F^s}(A,b)={\displaystyle \underset{i\in I}{\cap }{S}_{T_F^s}(a_i,b_i)}$.

Definition 1: For each $i\in I,$ we define $J_i=\left\{j\in J:a_{ij}\ge b_i\right\}.$

According to definition 1, we have the following lemmas, which are easily proved by the monotonicity and identity law of t-norms, definition 1 and the definition of Frank t-norm.

Lemma 1: Let $i\in I.$ If $j\notin J_i,$ then $T_F^s(a_{ij},x_j)<b_i,\forall x_j\in [0,1].$

Lemma 2: Let $i\in I$ and $j\in J_i.$

(a) If $x_j>{\log }_s\left(1+\frac{(s^{b_i}-1)(s-1)}{s^{a_{ij}}-1}\right)$ and $b_i\ne 0,$ then $T_F^s(a_{ij},x_j)>b_i.$

(b) If $x_j={\log }_s\left(1+\frac{(s^{b_i}-1)(s-1)}{s^{a_{ij}}-1}\right)$ and $b_i\ne 0,$ then $T_F^s(a_{ij},x_j)=b_i.$

(c) If $x_j<{\log }_s\left(1+\frac{(s^{b_i}-1)(s-1)}{s^{a_{ij}}-1}\right)$ and $b_i\ne 0,$ then $T_F^s(a_{ij},x_j)<b_i.$

(d) If $a_{ij}=b_i=0,$ then $T_F^s(a_{ij},x_j)=b_i,\forall x_j\in [0,1].$

(e) If $a_{ij}>b_i=0,$ then $T_F^s(a_{ij},x_j)=b_i$ for $x_j=0,$ and $T_F^s(a_{ij},x_j)>b_i$ for $0<x_j\le 1.$

Lemma 3 below gives a necessary and sufficient condition for the feasibility of sets $S_{T_F^s}(a_i,b_i),\forall i\in I.$

Lemma 3: For a fixed $i\in I,S_{T_F^s}(a_i,b_i)\ne \varnothing$ if and only if $J_i\ne \varnothing .$

Proof: The proof is similar to the proof of Lemma 3 in [15].

Definition 2: Suppose that $i\in I$ and $S_{T_F^s}(a_i,b_i)\ne \varnothing$ (hence, $J_i\ne \varnothing$ from lemma 3). Let ${\widehat{x}}_i=[{({\widehat{x}}_i)}_1,{({\widehat{x}}_i)}_2,\mathrm{...},{({\widehat{x}}_i)}_n]\in {[0,1]}^n$ where the components are defined as follows:

Also, for each $j\in J_i,$ we define ${\stackrel{⌣}{x}}_i(j)=[{\stackrel{⌣}{x}}_i{(j)}_1,{\stackrel{⌣}{x}}_i{(j)}_2,\mathrm{...},{\stackrel{⌣}{x}}_i{(j)}_n]\in {[0,1]}^n$ such that

The following theorem characterizes the feasible region of the i‘th relational equation $(i\in I).$

Theorem 1: Let $i\in I.$ If $S_{T_F^s}(a_i,b_i)\ne \varnothing ,$ then $S_{T_F^s}(a_i,b_i)={\displaystyle \underset{j\in J_i}{\cup }[{\stackrel{⌣}{x}}_i(j),{\widehat{x}}_i]}.$

Proof: For a more general case, see Corollary 2.3 in [21].

From theorem 1, ${\widehat{x}}_i$ is the unique maximum solution and ${\stackrel{⌣}{x}}_i(j)$‘s $(j\in J_i)$ are the minimal solutions of $S_{T_F^s}(a_i,b_i).$

Definition 3: Let ${\widehat{x}}_i(i\in I)$ be the maximum solution of $S_{T_F^s}(a_i,b_i).$ We define $\overline{X}=\underset{i\in I}{\min }\left\{{\widehat{x}}_i\right\}.$

Definition 4: Let $e:I\to J_i$ so that $e(i)=j\in J_i,\forall i\in I,$ and let $E$ be the set of all vectors $e$ . For the sake of convenience, we represent each $e\in E$ as an $m$ –dimensional vector $e=[j_1,j_2,\mathrm{...},j_m]$ in which $j_k=e(k).$

Definition 5: Let $e=[j_1,j_2,\mathrm{...},j_m]\in E.$ We define $\underset{\_}{X}(e)=[\underset{\_}{X}{(e)}_1,\underset{\_}{X}{(e)}_2,\mathrm{...},\underset{\_}{X}{(e)}_n]\in {[0,1]}^n,$ where $\underset{\_}{X}{(e)}_j=\underset{i\in I}{\max }\left\{{\stackrel{⌣}{x}}_i{(e(i))}_j\right\}=\underset{i\in I}{\max }\left\{{\stackrel{⌣}{x}}_i{(j_i)}_j\right\},\forall j\in J.$

From the relation $S_{T_F^s}(A,b)={\displaystyle \underset{i\in I}{\cap }{S}_{T_F^s}(a_i,b_i)}$ and Theorem 1, the following theorem is easily attained.

Theorem 2: $S_{T_F^s}(A,b)={\displaystyle \underset{e\in E}{\cup }[\underset{\_}{X}(e),\overline{X}]}.$

As a consequence, it turns out that $\overline{X}$ is the unique maximum solution and $\underset{\_}{X}(e)$'s $(e\in E)$ are the minimal solutions of $S_{T_F^s}(A,b).$ Moreover, we have the following corollary that is directly resulted from theorem 2.

Corollary 1(first necessary and sufficient condition): $S_{T_F^s}(A,b)\ne \varnothing$ if and only if $\overline{X}\in S_{T_F^s}(A,b)$ .

Example 1: Consider the problem below with Frank t-norm

where $\phi (x,y)=T_F^2(x,y)={\log }_2\left(1+(s^x-1)(s^y-1)\right)$ (i.e., $s=2$ ). By definition 1, we have $J_1=\left\{1,4\right\},J_2=\left\{1,5\right\},J_3=\left\{1,4,5\right\},J_4=\left\{4,5\right\}$ and $J_5=\left\{1,2,3,4,5,6\right\}.$ The unique maximum solution and the minimal solutions of each equation are obtained by definition 2 as follows, where 0.783316030456544 has been rounded to 0.7833:

${\widehat{x}}_1={\widehat{x}}_3=[\text{0}\text{.7833 , 1 , 1 , 1 , 1 , 1}],{\widehat{x}}_2={\widehat{x}}_4=[\text{1 , 1 , 1 , 1 , 1 , 1}],{\widehat{x}}_5=[\text{1 , 0 , 1 , 0 , 1 , 1}].$

${\stackrel{⌣}{x}}_1(1)=[\text{0}\text{.7833 , 0 , 0 , 0 , 0 , 0}],{\stackrel{⌣}{x}}_1(4)=[\text{0 , 0 , 0 , 1 , 0 , 0}]$

${\stackrel{⌣}{x}}_2(1)=[\text{1 , 0 , 0 , 0 , 0 , 0}],{\stackrel{⌣}{x}}_2(5)=[0\text{ , 0 , 0 , 0 , 1 , 0}]$

${\stackrel{⌣}{x}}_3(1)=[\text{0}\text{.7833 , 0 , 0 , 0 , 0 , 0}],{\stackrel{⌣}{x}}_3(4)=[\text{0 , 0 , 0 , 1 , 0 , 0}],{\stackrel{⌣}{x}}_3(5)=[0\text{ , 0 , 0 , 0 , 1 , 0}]$

${\stackrel{⌣}{x}}_4(4)=[\text{0 , 0 , 0 , 1 , 0 , 0}],{\stackrel{⌣}{x}}_4(5)=[\text{0 , 0 , 0 , 0 , 1 , 0}]$

${\stackrel{⌣}{x}}_5(j)=[\text{0 , 0 , 0 , 0 , 0 , 0}],j\in \left\{1,2,3,4,5,6\right\}$

Therefore, by theorem 1 we have

$S_{T_F^s}(a_1,b_1)=[{\stackrel{⌣}{x}}_1(1),{\widehat{x}}_1]\cup [{\stackrel{⌣}{x}}_1(4),{\widehat{x}}_1],$

$S_{T_F^s}(a_2,b_2)=[{\stackrel{⌣}{x}}_2(1),{\widehat{x}}_2]\cup [{\stackrel{⌣}{x}}_2(5),{\widehat{x}}_2],$

$S_{T_F^s}(a_3,b_3)=[{\stackrel{⌣}{x}}_3(1),{\widehat{x}}_3]\cup [{\stackrel{⌣}{x}}_3(4),{\widehat{x}}_3]\cup [{\stackrel{⌣}{x}}_3(5),{\widehat{x}}_3]$ and

$S_{T_F^s}(a_4,b_4)=[{\stackrel{⌣}{x}}_4(4),{\widehat{x}}_4]\cup [{\stackrel{⌣}{x}}_4(5),{\widehat{x}}_4]$ and

$S_{T_F^s}(a_5,b_5)=[0_{1\times 6},{\widehat{x}}_5]$ where $0_{1\times 6}$ is a zero vector. From definition 3, $\overline{X}=[\text{0}\text{.7833 , 0 , 1 , 0 , 1 , 1}].$ It is easy to verify that $\overline{X}\in S_{T_F^s}(A,b).$ Therefore, the above problem is feasible by corollary 1. Finally, the cardinality of set $E$ is equal to 24 (definition 4). So, we have 24 solutions $\underset{\_}{X}(e)$ associated to 24 vectors $e$ . For example, for $e=[1,5,1,5,6],$ we obtain $\underset{\_}{X}(e)=\max \left\{{\stackrel{⌣}{x}}_1(1),{\stackrel{⌣}{x}}_2(5),{\stackrel{⌣}{x}}_3(1),{\stackrel{⌣}{x}}_4(5),{\stackrel{⌣}{x}}_5(6)\right\}$ from definition 5 that means $\underset{\_}{X}(e)=[\text{0}\text{.7833 , 0 , 0 , 0 , 1 , 0}].$

In practice, there are often some components of matrix $A$ that have no effect on the solutions to problem (1). Therefore, we can simplify the problem by changing the values of these components to zeros. For this reason, various simplification processes have been proposed by researchers. We refer the interesting reader to [21] where a brief review of such these processes is given. Here, we present two simplification techniques based on the Frank t-norm.

Definition 6: If a value changing in an element, say $a_{ij}$ , of a given fuzzy relation matrix $A$ has no effect on the solutions of problem (1), this value changing is said to be an equivalence operation.

Corollary 2: Suppose that $T_F^s(a_{i{j}_0},x_{j_0})<b_i,\forall x\in S_{T_F^s}(A,b).$ In this case, it is obvious that $\underset{j=1}{\overset{n}{\max }}\left\{T_F^s(a_{ij},x_j)\right\}=b_i$ is equivalent to $\underset{\begin{array}{l}j=1\\ j\ne j_0\end{array}}{\overset{n}{\max }}\left\{T_F^s(a_{ij},x_j)\right\}=b_i,$ that is, “resetting $a_{i{j}_0}$ to zero” has no effect on the solutions of problem (1) (since component $a_{i{j}_0}$ only appears in the i‘th constraint of problem (1)). Therefore, if $T_F^s(a_{i{j}_0},x_{j_0})<b_i,\forall x\in S_{T_F^s}(A,b),$ then “resetting $a_{i{j}_0}$ to zero” is an equivalence operation.

Lemma 4 (first simplification): Suppose that $j_0\notin J_i,$ for some $i\in I$ and $j_0\in J.$ Then, “resetting $a_{i{j}_0}$ to zero” is an equivalence operation.

Proof: From corollary 2, it is sufficient to show that $T_F^s(a_{i{j}_0},x_{j_0})<b_i,\forall x\in S_{T_F^s}(A,b).$ But, from lemma 1 we have $T_F^s(a_{i{j}_0},x_{j_0})<b_i,\forall x_{j_0}\in [0,1].$ Thus $T_F^s(a_{i{j}_0},x_{j_0})<b_i,\forall x\in S_{T_F^s}(A,b).$

Lemma 5 (second simplification): Suppose that $j_0\in J_{i_1}$ and $b_{i_1}\ne 0,$ where $i_1\in I$ and $j_0\in J.$ If at least one of the following conditions hold, then “resetting $a_{i_1{j}_0}$ to zero” is an equivalence operation:

(a) There exists some $i_2\in I(i_1\ne i_2)$ such that $j_0\in J_{i_2},b_{i_2}\ne 0$ and ${\log }_s\left(1+(s^{b_{i_2}}-1)(s-1)/(s^{a_{i_2{j}_0}}-1)\right)<{\log }_s\left(1+(s^{b_{i_1}}-1)(s-1)/(s^{a_{i_1{j}_0}}-1)\right).$

(b) There exists some $i_2\in I(i_1\ne i_2)$ such that $a_{i_2{j}_0}>0.$

Proof: (a) Similar to the proof of lemma 4, we show that $T_F^s(a_{i_1{j}_0},x_{j_0})<b_i,\forall x\in S_{T_F^s}(A,b).$ Consider an arbitrary feasible solution $x\in S_{T_F^s}(A,b).$ Since $x\in S_{T_F^s}(A,b),$ it turns out that $T_F^s(a_{i_1{j}_0},x_{j_0})>b_{i_1}$ never holds. So, assume that $T_F^s(a_{i_1{j}_0},x_{j_0})=b_{i_1},$ that is ${\log }_s\left(1+(s^{a_{i_1{j}_0}}-1)(s^{x_{j_0}}-1)/(s-1)\right)=b_{i_1}.$ Since $b_{i_1}\ne 0,$ from lemma 2 we conclude that $x_{j_0}={\log }_s\left(1+(s^{b_{i_1}}-1)(s-1)/(s^{a_{i_1{j}_0}}-1)\right).$ So, by the assumptionwe have ${\log }_s\left(1+(s^{b_{i_2}}-1)(s-1)/(s^{a_{i_2{j}_0}}-1)\right)<x_{j_0}.$ Therefore, lemma 2 (part (a)) implies $T_F^s(a_{i_2{j}_0},x_{j_0})>b_{i_2}$ that contradicts $x\in S_{T_F^s}(A,b).$

(b) By the assumption, we have $j_0\in J_{i_2}.$ Now, the result similarly follows by a simpler argument.

Example 2: Consider the problem presented in example 1. From the first simplification (lemma 4), “resetting the following components $a_{ij}$ to zeros” are equivalence operations: $a_{12},a_{13},a_{15},a_{16};a_{22},a_{23},a_{24},a_{26};a_{32},a_{33},a_{36};a_{41},a_{42},a_{43},a_{46};$ in all of these cases, $a_{ij}<b_i,$ that is $j\notin J_i.$ Also, from the second simplification (lemma 5, part (a)), we can change the value of component $a_{21}$ to zero; because $a_{21}=b_2$ (i.e., $1\in J_2$ ), $b_2\ne 0,a_{11}>b_1$ (i.e. $1\in J_1$), $b_1\ne 0$ and $\text{0}\text{.7833}={\log }_s\left(1+(s^{b_1}-1)(s-1)/(s^{a_{11}}-1)\right)<{\log }_s\left(1+(s^{b_2}-1)(s-1)/(s^{a_{21}}-1)\right)=1$ . Moreover, from lemma 5 (part (b)), we can also change the values of components $a_{14},a_{34}$ and $a_{44}$ to zeros with no effect on the solutions set of the problem (since $4\in J_1\cap J_3\cap J_4,b_i\ne 0\text{ (}i=1,3,4),$ and $b_5=0$ $a_{54}>0).$

In addition to simplifying the problem, a necessary and sufficient condition is also derived from lemma 5. Before formally presenting the condition, some useful notations are introduced. Let $\tilde{A}$ denote the simplified matrix resulted from $A$ after applying the simplification processes (lemmas 4 and 5). Also, similar to definition 1, assume that ${\tilde{J}}_i=\left\{j\in J:{\tilde{a}}_{ij}\ge b_i\right\}(i\in I)$ where ${\tilde{a}}_{ij}$ denotes $(i,j)$ ‘th component of matrix $\tilde{A}$. The following theorem gives a necessary and sufficient condition for the feasibility of problem (1).

Theorem 3 (second necessary and sufficient condition): $S_{T_F^s}(A,b)\ne \varnothing$ if and only if ${\tilde{J}}_i\ne \varnothing ,\forall i\in I.$

Proof: Since $S_{T_F^s}(A,b)=S_{T_F^s}(\tilde{A},b)$ from lemmas 4 and 5, it is sufficient to show that $S_{T_F^s}(\tilde{A},b)\ne \varnothing$ if and only if ${\tilde{J}}_i\ne \varnothing ,\forall i\in I.$ Let $S_{T_F^s}(\tilde{A},b)\ne \varnothing .$ Therefore, $S_{T_F^s}({\tilde{a}}_i,b_i)\ne \varnothing ,\forall i\in I,$ where ${\tilde{a}}_i$ denotes i ‘th row of matrix $\tilde{A}.$ Now, lemma 3 implies ${\tilde{J}}_i\ne \varnothing ,\forall i\in I.$ Conversely, suppose that ${\tilde{J}}_i\ne \varnothing ,\forall i\in I.$ Again, by using lemma 3 we have ${\tilde{J}}_i\ne \varnothing ,\forall i\in I.$ By contradiction, suppose that $S_{T_F^s}(\tilde{A},b)=\varnothing .$ Therefore, $\overline{X}\notin S_{T_F^s}(\tilde{A},b)$ from corollary 1, and then there exists $i_0\in I$ such that $\overline{X}\notin S_{T_F^s}({\tilde{a}}_{i_0},b_{i_0}).$ Since $\underset{j\notin {\tilde{J}}_i}{\max }\left\{T_F^s({\tilde{a}}_{i_{0}j},{\overline{X}}_j)\right\}<b_{i_0}$ (from lemma 1) , we must have either $\underset{j\in {\tilde{J}}_i}{\max }\left\{T_F^s({\tilde{a}}_{i_{0}j},{\overline{X}}_j)\right\}>b_{i_0}$ or $\underset{j\in {\tilde{J}}_i}{\max }\left\{T_F^s({\tilde{a}}_{i_{0}j},{\overline{X}}_j)\right\}<b_{i_0}.$ Anyway, since $\overline{X}\le {\widehat{x}}_{i_0}$ (i.e., ${\overline{X}}_j\le {({\widehat{x}}_{i_0})}_j,\forall j\in J),$ we have $\underset{j\in {\tilde{J}}_{i_0}}{\max }\left\{T_F^s({\tilde{a}}_{i_{0}j},{\overline{X}}_j)\right\}\le \underset{j\in {\tilde{J}}_{i_0}}{\max }\left\{T_F^s({\tilde{a}}_{i_{0}j},{({\widehat{x}}_{i_0})}_j)\right\}=b_{i_0},$ and then the former case (i.e.,$\underset{j\in {\tilde{J}}_i}{\max }\left\{T_F^s({\tilde{a}}_{i_{0}j},{\overline{X}}_j)\right\}>b_{i_0}$) never holds. Therefore, $\underset{j\in {\tilde{J}}_i}{\max }\left\{T_F^s({\tilde{a}}_{i_{0}j},{\overline{X}}_j)\right\}<b_{i_0}$ that implies $b_{i_0}\ne 0$ and $T_F^s({\tilde{a}}_{i_{0}j},{\overline{X}}_j)<b_{i_0},\forall j\in {\tilde{J}}_{i_0}.$ Hence, by lemma 2, we must have ${\overline{X}}_j<{\log }_s\left(1+(s^{b_{i_0}}-1)(s-1)/(s^{{\tilde{a}}_{i_{0}j}}-1)\right),\forall j\in {\tilde{J}}_{i_0}.$ On the other hand, ${\log }_s\left(1+(s^{b_{i_0}}-1)(s-1)/(s^{{\tilde{a}}_{i_{0}j}}-1)\right)\le 1,\forall j\in {\tilde{J}}_{i_0}.$ Therefore, ${\overline{X}}_j<1,\forall j\in {\tilde{J}}_{i_0},$ and then from definitions 2 and 3, for each $j\in {\tilde{J}}_{i_0}$ there must exists $i_j\in I$ such that either $j\in {\tilde{J}}_{i_j}$ and ${\overline{X}}_j={({\widehat{x}}_{i_j})}_j={\log }_s\left(1+(s^{b_{i_j}}-1)(s-1)/(s^{{\tilde{a}}_{i_{j}j}}-1)\right)$ or $j\in {\tilde{J}}_{i_j}$ and ${\tilde{a}}_{i_{j}j}>b_{i_j}=0.$ Until now, we proved that $b_{i_0}\ne 0$ and for each $j\in {\tilde{J}}_{i_0},$ there exist $i_j\in I$ such that either $j\in {\tilde{J}}_{i_j}$ and ${\log }_s\left(1+(s^{b_{i_j}}-1)(s-1)/(s^{{\tilde{a}}_{i_{j}j}}-1)\right)<{\log }_s\left(1+(s^{b_{i_0}}-1)(s-1)/(s^{{\tilde{a}}_{i_{0}j}}-1)\right)$ (because, ${\log }_s\left(1+(s^{b_{i_j}}-1)(s-1)/(s^{{\tilde{a}}_{i_{j}j}}-1)\right)={\overline{X}}_j<{\log }_s\left(1+(s^{b_{i_0}}-1)(s-1)/(s^{{\tilde{a}}_{i_{0}j}}-1)\right)$) or $b_{i_j}=0$ ${\tilde{a}}_{i_{j}j}>0.$ But in both cases, we must have ${\tilde{a}}_{i_{0}j}=0(\forall j\in {\tilde{J}}_{i_0})$ from the parts (a) and (b) of lemma 5, respectively. Therefore, ${\tilde{a}}_{i_{0}j}<b_{i_0}\ne 0(\forall j\in {\tilde{J}}_{i_0})$ that is a contradiction.

Remark 1: Since $S_{T_F^s}(A,b)=S_{T_F^s}(\tilde{A},b)$ (from lemmas 4 and 5), we can rewrite all the previous definitions and results in a simpler manner by replacing ${\tilde{J}}_i$ with $J_i(i\in I).$

In this section, the genetic algorithm proposed in [15] is briefly discussed. Since the feasible region of problem (1) is non-convex, a convex subset of the feasible region is firstly introduced. Consequently, the proposed GA can easily generate the initial population by randomly choosing individuals from this convex feasible subset. At the last part of this section, a method is presented to generate random feasible max-Yager fuzzy relational equations.

The initial population is given by randomly generating the individuals inside the feasible region. For this purpose, we firstly find a convex subset of the feasible solutions set, that is, we find set $F$ such that $F\subseteq S_{T_Y^p}(A,b)$ and $F$ is convex. Then, the initial population is generated by randomly selecting individuals from set $F$.

Definition 7: Suppose that $S_{T_F^s}(\tilde{A},b)\ne \varnothing .$ For each $i\in I,$ let ${\stackrel{⌣}{x}}_i=[{({\stackrel{⌣}{x}}_i)}_1,{({\stackrel{⌣}{x}}_i)}_2,\mathrm{...},{({\stackrel{⌣}{x}}_i)}_n]\in {[0,1]}^n$ where the components are defined as follows:

Also, we define $\underset{\_}{X}=\underset{i\in I}{\max }\left\{{\stackrel{⌣}{x}}_i\right\}.$

Remark 2: According to definition 2 and remark 1, it is clear that for a fixed $i\in I$ and $j\in {\tilde{J}}_i,{\stackrel{⌣}{x}}_i{(j)}_k\le {({\stackrel{⌣}{x}}_i)}_k(\forall k\in J).$ Therefore, from definitions 5 and 7 we have $\underset{\_}{X}{(e)}_k=\underset{i\in I}{\max }\left\{{\stackrel{⌣}{x}}_i{(e(i))}_k\right\}=\underset{i\in I}{\max }\left\{{\stackrel{⌣}{x}}_i{(j_i)}_k\right\}\le \underset{i\in I}{\max }\left\{{({\stackrel{⌣}{x}}_i)}_k\right\}={\underset{\_}{X}}_k,\forall k\in J$ and $\forall e\in E.$ Thus $\underset{\_}{X}(e)\le \underset{\_}{X},\forall e\in E.$

Example 3: Consider the problem presented in example 1, where $\overline{X}=[\text{0}\text{.7833 , 0 , 1 , 0 , 1 , 1}].$ Also, according to example 2, the simplified matrix $\tilde{A}$ is

From definition 7, we have ${\stackrel{⌣}{x}}_1=[\text{0}\text{.7833 , 0 , 0 , 0 , 0 , 0}],{\stackrel{⌣}{x}}_2=[0\text{ , 0 , 0 , 0 , 1 , 0}],$ ${\stackrel{⌣}{x}}_3=[\text{0}\text{.7833 , 0 , 0 , 0 , 1 , 0}],{\stackrel{⌣}{x}}_4=[\text{0 , 0 , 0 , 0 , 1 , 0}],{\stackrel{⌣}{x}}_5=[\text{0 , 0 , 0 , 0 , 0 , 0}]$, and then $\underset{\_}{X}=\underset{i=1}{\overset{5}{\max }}\left\{{\stackrel{⌣}{x}}_i\right\}=[\text{0}\text{.7833 , 0 , 0 , 0 , 1 , 0]}\text{.}$ Therefore, set $F=[\underset{\_}{X},\overline{X}]$ is obtained as a collection of intervals:

By generating random numbers in the corresponding intervals, we acquire one initial individual: $x=[\text{0}\text{.7833 , 0 , 0}\text{.6 , 0 , 1 , 0}\text{.2}\text{]}\text{.}$

The algorithm for generating the initial population is simply obtained as follows:

Algorithm 1 (Initial Population):
$$\begin{array}{l}\text{1}\text{. Get fuzzy matrix }A\text{, fuzzy vector }b\text{and population size }{S}_{pop}\text{.}\\ \text{2}\text{. If }\overline{X}\notin S_{T_F^s}(A,b)\text{, then stop; the problem is infeasible (corollary1)}\text{.}\\ \text{3}\text{. For i}=\text{1,2,}\mathrm{...}\text{,}{S}_{pop}\\ \text{Generate a random }n-\text{dimensional solution }pop(i)\text{in the interval }[\underset{\_}{X},\overline{X}].\\ \text{End}\end{array}$$

Suppose that the individuals in the population are sorted according to their ranks from the best to worst, that is, individual $pop(r)$ has rank $r.$ The probability $P_r$ of choosing the $r$ ‘th individual is given by the following formulas:

where the weight to be a value of the Gaussian function with argument $r,$ mean 1 , and standard deviation $q{S}_{pop},$ where $q$ is a parameter of the algorithm.

As usual, suppose that $S_{T_F^s}(A,b)\ne \varnothing .$ So, from theorem 3 we have ${\tilde{J}}_i\ne \varnothing ,\forall i\in I,$ Where ${\tilde{J}}_i=\left\{j\in J:{\tilde{a}}_{ij}\ge b_i\right\},\forall i\in I$ (see definition1 and remark 1).

Definition 8: Let $I^{+}=\left\{i\in I:b_i\ne 0\right\}.$ So, we define $D=\left\{j\in J:\text{if }\exists i\in I^{+}\text{such that}j\in {\tilde{J}}_i\Rightarrow \left|{\tilde{J}}_i\right|>1\right\},$ where $\left|{\tilde{J}}_i\right|$ denotes the cardinality of set ${\tilde{J}}_i.$

The mutation operator is defined as follows:

$$\begin{array}{l}\text{1}\text{. Get the matrix }\tilde{A}\text{, vector }b\text{and a selected solution }\dot{x}=[{\dot{x}}_1,\mathrm{...},{\dot{x}}_n]\text{.}\\ \text{2}\text{. While }D\ne \varnothing \\ \text{ 2}\text{.1}\text{. Set }{x}^{\prime }\leftarrow x\text{.}\\ \text{ 2}\text{.2}\text{. Randomly choose }{j}_0\in D,\text{and set }{x^{\prime }}_{j_0}=0.\\ \text{2}\text{.3}\text{. IF }{x}^{\prime }\text{ is feasible, go to Crossover operator; otherwise, set }D=D-\left\{j_0\right\}\text{. }\end{array}$$

In section 2, it was proved that $\overline{X}$ is the unique maximum solution of $S_{T_F^s}(A,b).$ By using this result, the crossover operator is stated as follows:

$$\begin{array}{l}\text{1}\text{. Get the maximum solution }\overline{X}\text{, the new solution }{x}^{\prime }\text{(generated by algorith 2) }\\ \text{ and one parent }pop(k)(\text{for some }k=1,2,\mathrm{...},S_{pop})\text{.}\\ \text{2}\text{. Generate a random number }{\lambda }_1\in [0,1]\text{. Set }{x}_{new1}={\lambda }_1{x}^{\prime }+(1-{\lambda }_1)\overline{X}.\\ 3.\text{Let }{\lambda }_2=\underset{\begin{array}{l}j=1\\ j\ne k\end{array}}{\overset{S_{pop}}{\min }}\Vert pop(k)-pop(j)\Vert \text{ and }d=\overline{X}-pop(k)\text{.}\\ \text{ Set }{x}_{new2}=pop(k)+\min \left\{{\lambda }_2,1\right\}d.\end{array}$$

There are usually several ways to generate a feasible FRE defined with different t-norms. In what follows, we present a procedure to generate random feasible max-Frank fuzzy relational equations:

$$\begin{array}{l}\text{1}\text{. Randomly select }m\text{ columns {}{j}_1\text{, }{j}_2\text{,}\mathrm{...}\text{, }{j}_m\text{}}\text{from }J\text{=}\left\{1\text{,}2\text{,}\mathrm{...}\text{,}n\right\}\text{.}\\ \text{2}\text{. Generate vector }b\text{ whose elements are random numbers from [0,1]}\text{.}\\ \text{3}\text{. For }i\in \left\{\text{1,2,}\mathrm{...}\text{,}m\right\}\\ \text{Assign a random number from [}{b}_i\text{,1] to }{a}_{i{j}_i}.\\ \text{End}\\ \text{4}\text{. For }i\in \left\{\text{1,2,}\mathrm{...}\text{,}m\right\}\\ \text{ For each }k\in \left\{\text{1,2,}\mathrm{...}\text{,}m\right\}-\left\{i\right\}\\ \text{If }{b}_k\text{=0}\\ \text{ Set }{a}_{k{j}_i}=0.\\ \text{ Else}\\ \text{ Assign a random number from [0 , }{\log }_s\left(1+(s^{b_k}-1)(s^{a_{i{j}_i}}-1)/(s^{b_i}-1)\right)\text{] to }{a}_{k{j}_i}.\\ \text{ End}\\ \text{ End}\\ \text{ End}\\ \text{5}\text{. For each }i\in \left\{\text{1,2,}\mathrm{...}\text{,}m\right\}\text{and each }j\notin \text{{}{j}_1\text{, }{j}_2\text{,}\mathrm{...}\text{, }{j}_m\text{} }\\ \text{ Assign a random number from [}0\text{,1] to }{a}_{ij}.\\ \text{ End}\end{array}$$

By the following theorem, it is proved that algorithm 4 always generates random feasible max-Frank fuzzy relational equations.

Theorem 4: The solutions set $S_{T_F^s}(A,b)$ of FRE (with Frank t-norm) constructed by algorithm 4 is not empty. Proof. According to step 3 of the algorithm, $j_i\in J_i,\forall i\in I.$ Therefore, $J_i\ne \varnothing ,\forall i\in I.$ To complete the proof, we show that $j_i\in {\tilde{J}}_i,\forall i\in I.$ By contradiction, suppose that the second simplification process reset $a_{i{j}_i}$ to zero, for some $i\in I.$ So, $b_i\ne 0$ and there must exists some $k\in I(k\ne i)$ such that either $j_i\in J_k,b_k\ne 0$ and ${\log }_s\left(1+(s^{b_k}-1)(s-1)/(s^{a_{k{j}_i}}-1)\right)<{\log }_s\left(1+(s^{b_i}-1)(s-1)/(s^{a_{i{j}_i}}-1)\right)$ or $b_k=0$ and $a_{k{j}_i}>0.$ In the former case, we note that $a_{k{j}_i}>{\log }_s\left(1+(s^{b_k}-1)(s^{a_{i{j}_i}}-1)/(s^{b_i}-1)\right).$ Anyway, both cases contradict step 4.