{'fraction_non_alphanumeric': 0.029045643153526972, 'fraction_numerical': 0.011050893386400203, 'mean_word_length': 5.034491568727645, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Solution for Large Scale Optimization Problems Based on Gravitational Search Algorithm

One of the challenges in optimization of high dimensional problems is finding appropriate solutions in a way that are as close as possible to the global optima. In this regard, one of the most common phenomena that occurs is the curse of dimensionality in which a large scale feature space generates more parameters that need to be estimated. Heuristic algorithms, such as Gravitational Search Algorithm, are among the tools proposed for optimizing large-scale problems, but in this case, they cannot solve the problem on their own. This paper proposes a novel method for optimizing large scale problems by improving the gravitational search algorithm's performance. In order to increase the efficiency of the gravitational search algorithm in solving large scale problems, the proposed method combines this algorithm with the cooperative-coevolution methods. For the evaluation of the performance of the proposed algorithm, we consider two approaches. In the first approach, the proposed algorithm is compared with the gravitational search algorithm, and in the second approach, it is compared with some of the most significant research in this field. In the first approach, our method was able to improve the performance of the original gravitational algorithm to solve large scale problems, and in the second one, the results indicate more favorable performance, in some benchmark functions, compared with other cooperative methods.


Introduction
Meta Heuristic algorithms are a branch of optimization algorithms that are inspired by nature and have the capability to search high dimensional spaces. During the last decades, different types of meta heuristic algorithms have been introduced. Some of these algorithms are: Artificial Bee Colony (ABC) [1], Ant Colony Optimization (ACO) [2], Particle Swarm Optimization (PSO) [3], an improved Shuffled Frog-leaping Algorithm (SFL) [4], Grenade Explosion Method (GME) [5], Artificial Immune System [6], Gravitational Search Algorithm (GSA) [7], and Whale Optimization Algorithm [8].
The gravitational search algorithm is one of the newest heuristic algorithms proposed by Rashedi and Nezam Abadipour in recent years, which is inspired by the concepts of mass and gravity by simulating Newton's laws of gravity and motion. This algorithm's features include simple implementation, the generality of the concept, and its ability to achieve global optimality, which have made it successful [6].
This algorithm is known as one of the most powerful and reliable search tools for the best solution, but as optimization problems become more complex and larger, researchers face new challenges in responding to the increasing computational needs of using this algorithm.
Optimization is one of the most important issues in the field of Computer Science, Artificial Intelligence, Soft Computing, and Machine Vision. In optimization, looking for the best solution in a reasonable time is desired [3][4][5][6][7][8][9]. Evolutionary algorithms have successfully solved most of the optimization problems, although their performance is weak in tackling high dimensional problems. Since the search space of a problem increases exponentially with the size of the problem, most of the evolutionary algorithms suffer from the "Curse of dimensionality." In this condition, the evolutionary algorithm is stuck in a local optimum and cannot find the global optimum [10].
In high dimensional problems, everything becomes much harder when we are facing with nonseparable problems and interacting variables. For handling the obstacles related to the high dimensional problems, two categories of methods have been introduced. The first category is 2 Banifakhr Mojtaba , 1 Somayeh Seifi Shalamzari Cooperative Co-evolutionary methods, and the second one is non Cooperative Coevolutionary methods. Cooperative Co-evolutionary (CC) approach is inspired by the divide and conquer method [10]. CC is a combination method that consists of two phases; the first phase is the grouping stage, and the second phase is the optimization stage. In the grouping stage, a high dimensional problem is decomposed into subcomponents and in the optimization stage, each subcomponent is optimized by an evolutionary algorithm. Since the most important stage in the CC method is the grouping stage, a suitable grouping strategy will guide the problem to the global optimum. The best grouping method is one which puts the interacting variables in the same subcomponents.
Formerly, CC has been applied to many evolutionary algorithms with different grouping methods to solve large scale problems. For the first time, CCGA, a combination of the CC method and the genetic algorithm, was introduced by Potter and Jong [10]. In their method, a problem with n variables was decomposed to n subgroups with one variable in each subgroup. F. Vandenberg applied CC to the Particle Swarm Optimization (PSO) algorithm [11] . In the grouping stage, the problems were decomposed to k subcomponents with s variables in each subcomponent. Liu applied CC to Fast Evolutionary Programming (FEP), but this algorithm was trapped in a local optimum in one of the non-separable functions [12]. Yang introduced a new grouping strategy, named Random Grouping, and applied it to the Differential Evolution (DE) [13]. Random Grouping increased the possibility of laying two interacting variables in the same group. However, when the number of interacting variables increased, the possibility decreased. As a result, Omidvar introduced Frequently Random Grouping, which increased this possibility [14]. The performance of Frequent Random Grouping deteriorated when the number of interacting variables went beyond 5 variables.
To handle it, Omidvar presented Delta Grouping [15] but it showed weak performance where there were more than one non-separable subcomponents.
To solve this issue, Omidvar introduced a new grouping strategy, named Differential Grouping, and applied CC with Differential Grouping to the Differential Evolution [16]. The differential grouping had a great performance to handle interacting variables.
In [17], EADE, which is a non-Cooperative Coevolution method, has been introduced. This method is a modified version of the deferential evaluation algorithm (DE). However, in EADE, the mutation and crossover operators have been improved to be suitable for tackling large scale problems.
In this paper, we applied differential grouping, as a grouping strategy in the CC method, to the GSA to improve its performance in facing large scale problems. Since, thus far, the Gravitational Search Algorithm has not been applied to large scale optimization problems, the proposed method is innovative.
The remainder of this paper is arranged as follows.
In section II the standard gravitational search algorithm is introduced. In section III the proposed method for tackling high dimensional problems is given. Section IV presents the results and comparison with the standard GSA. In the results, the comparison of our method with several Cooperative Co-evolutionary methods and one of the non Cooperative methods is presented. Finally, section V concludes the paper.

Research Foundations
As mentioned in the previous section, optimization is one of the most important issues for researchers in various fields. The structures proposed based on the evolutionary algorithms have good results in many optimization problems, but these results weaken as the number of dimensions increases. Today, with the advancement of various sciences and technologies, due to the larger scale of the problems and search space, the need for large scale optimization is arised.
It should be noted that when the search space grows, most optimization problems suffer from the curse of dimensionality, which deteriorates the performance of these methods [3][4][5][6][7][8]. One of the important factors that challenge large scale problems is that the increasing number of variables leads to an exponential increase in the problem space. In addition, characteristics may change as the scale of the problem space increases. Another challenge is the costly evaluation of large scale problems, and the last challenge is the existence of an interaction between variables.

Cooperative Co-evolutionary (CC) Method
The Cooperative Co-evolutionary method is a new method based on and inspired by the divide-andconquer method, in which a large scale problem is divided into smaller scale subcomponents, and each subcomponent is optimized by a specific evolutionary algorithm (EA). In the CC method, the kind of grouping method we choose has a great impact on the optimization's performance. The better grouping we provide, the better the problem can be optimized and the probability of placing interacting variables in a group can be increased.
The hybrid optimization method with the CC method consists of two stages. In the first stage, grouping, the problem is grouped by applying one of the grouping methods, and thus subcomponents are formed. Then in the second stage, optimization, each of these subcomponents is optimized with a specific EA.
In the Gravitational Search Algorithm, optimization is performed with the help of the laws of gravity and motion in a discrete-time artificial system [6]. The system environment is the same as the scope of the problem definition. According to the law of gravitation, every mass perceives other masses' location and status through the law of gravitational attraction. Therefore, this force can be used as a tool to exchange information in space. The amount of masses is determined based on the objective function. The gravitational search algorithm is described in two general steps: in the first step, a discrete-time artificial system is formed in the problem environment, initial positioning of masses is determined, governing rules are defined, and parameters are set, and in the second step, the passage of time, the motion of masses, and the updating of parameters happen until it reaches the stop time.

Gravitational Search Algorithm
Gravitational Search Algorithm, which is a population-based optimization algorithm, is inspired by Newton's laws of gravity and motion [6]. Referred to [6], the mass of every agent is computed using the fitness of the population (for a minimization problem), as shown in Eq (1,2): (1) Where N, ( ) ( ) represent the size of the population, the mass, and fitness of the i th agent, resepctively. Worst (t) and best (t) are calculated (for a minimization problem) based on Eq (3,4).
Total forces of heavier masses applied to an agent based on the laws of gravity and motion [18] in Eq (5-7) is used to compute the acceleration of an agent as shown in Eq (6). The next velocity, which is a fraction of the current velocity added to the acceleration is calculated in Eq (7). The next position of an agent will be calculated based on Eq (8): In these formulas, , and respectively depict the acceleration, velocity, and position of the i th agent in d th dimension. and are random numbers in the interval [0,1]. Epsilon is a small number, n is the dimension of the search space and R is the Euclidean distance between two agents. Agents with the best fitness and the greatest masses are presented by Kbest. Kbest is initialized by K0 equal to N and decreases linearly to 1 by time.
G is initialized by G0 and decreases exponentially to zero by time. The block diagram of the standard GSA is presented in figure 1.  [19], Disruption: a new operator in gravitational search algorithm [20], a quantum version of gravitational search algorithm [21], and Black hole: a new operator for gravitational search algorithm [22].

Proposed Method
As mentioned earlier, the GSA algorithm was only suitable for small scale functions. Therefore, for larger-scale problems, an algorithm is needed that could cross local minima in addition to having a good convergence speed.
Like other cooperative co-evolutionary methods, the proposed method consists of two stages: in the first stage, the grouping is performed, and then in the next stage, optimization is conducted.
In the grouping stage, any of the grouping methods described can be used. As stated earlier, the differential grouping algorithm is the best grouping method, as in this algorithm, the interacting variables are most likely to fall in the same subgroup. Therefore, the proposed method uses the differential grouping algorithm in the grouping stage. In this method, first, the differential grouping algorithm is used to separate dimensions, and then the GSA algorithm, which provides an acceptable solution compared to other metahuristic algorithms, is used as the optimizer.
Accordingly, the fitness value calculated in the current algorithm has a significant advantage over the GSA. The difference between the proposed method and other cooperative co-evolutionary methods is that in this implemented algorithm, first, the optimizer function is different, and thus, the inputs and outputs are slightly different, and second, each time the optimization per column (dimension) is performed, the best value obtained is stored in the corresponding column and in a variable. According to the approach of using differential grouping, the calculated groups are independent of each other. Therefore, in the calculation, each column can be optimized independently. A noteworthy point in the proposed algorithm is that each time the algorithm is executed, the best member of the population is identified, and then a population is constructed in the optimizer function that has the size of the main population, and also all the rows of this population are made up of this best member. In the optimization phase, the subgroup to which the optimizer function is to be applied takes its place in this new population, and the optimizer function applies only to this subgroup. the advantage of this proximity to the best member is that with consecutive iterations of the algorithm, all the population members move toward this best member. Using the above algorithm, although the computation time increases slightly, by looking at the convergence diagrams, one can see that this trend gets better in most diagrams. It should be noted that in some diagrams, convergence sometimes declines, but then it is observed that the previous decline is offset and moves toward improvement. As can be deduced from the pseudocode presented in Fig. 2, the stated operation is reiterated by the number of cycles.

Simulations
In the previous section, a hybrid CCGSA-DG algorithm was introduced in which differential grouping is used as a proper grouping algorithm. In this section, this algorithm is compared with other algorithms. This comparison is performed in two stages. In the first stage, the algorithm is compared with the standard GSA. The benchmark functions available in [1] are used for this purpose. In the second stage, the proposed method is compared with the following algorithms: DECC-DG [16], MLCC [23], DECC-D [15], DECC-DML [15], and EADE [17].

4-1 Comparison of CCGSA-DG with the standard GSA
In this section, the benchmark functions available in [1] are employed for evaluation. There are 24 benchmark functions, among which 13 functions, F1 to F13, can have different number of variables, but other functions, F14 to F23, have a fixed number of variables. Functions F1 to F7 are unimodal, in which the convergence rate of the searching algorithm is more important than the final answer, and functions F8 to F13 are multimodal, in which number of minimums for the above functions increases exponentially as the number of dimensions increases, making the problem more complex. The list of unimodal and multimodal functions used in this experiment is given in tables 1 and 2. Since we tend to examine the existing algorithm's performance on large scale functions and compare it with other cooperative algorithms of this field, this algorithm is first applied only to some specific benchmark functions from [1], and then it is applied to all 2010 benchmark functions [3] for comparison with other cooperative algorithms. In this table, n, S, and fopt indicate the search space dimension, search space region, and the optimal value, respectively.   In the GSA algorithm applied in CCGSA-DG, the population size (N) and the maximum iterations were considered 50 and 500, respectively. In equation G used in GSA, the constant G0 is considered 100 and ∝ is considered equal to 20.  In the simulation conducted in this section, the maximum of the cycles that optimization is applied to subgroups is considered equal to 20. Figure 3 shows the results obtained from applying the proposed CCGSA-DG algorithm on functions with 30, 500, and 1000 dimensions. As the obtained convergence process of figures and optimal value show, the resulting algorithm has provided favorable results. As can be concluded from the above figure, convergence graphs for 500 dimensions, which is a lot more than that of the original GSA, have presented acceptable results and convergence.
As we have stated, the gravitational algorithm has not been applied to functions with high dimensions. According to the graphs, the suggested algorithm has represented good results on functions with 1000 dimensions.

4-2 Comparing the CCGSA-DG algorithm with existing algorithms in the field of CC
In this section, the suggested algorithm is compared with algorithms DECC-DG, MLCC, DECC-DML, DECC-D, and EADE. The benchmark functions employed in this section are 2010 benchmark functions [10] written for functions with high dimensions. The proposed algorithm was applied to these functions with 1000 dimensions. The 2010 benchmark functions are usually used for problems with high dimensions. These functions are designed in such a way that they solve four types of large scale problems. In the first group, separable functions are used as benchmark functions, which include functions F1 to F3. In the second group, the partial separable functions are used as benchmark functions. In these functions, there is a non-separable subcomponent with 50 variables and a separable group consisting of 950 variables. Functions F4 to F8 belong to this group. In the third group, some functions include 10 non-separable subcomponents, each containing 50 variables, and a separable subcomponent with 500 variables. Functions F9 to F13 belong to this group. The fourth group contains functions that include 20 non-separable subcomponents, each with 50 variables. Functions F14 to F18 are in this group. The last group includes functions that are completely non-separable and contain functions F19 to F20.
In all the functions, the search space dimensions are considered to be equal to 1000, and p is a random permutation of set {1, 2, …, D}. In Table 4, the performance of the proposed method compared to other methods considered in the second approach can be observed by taking into account the abovementioned benchmark function.  The convergence graphs associated with existing functions are given in figure 4. In the top, middle, and bottom figures, the convergence graphs are shown for dimension equal to 1000.

4-3 Results
For the first considered approach in this paper, the GSA's ability to solve problems with high dimensions is improved by applying CC to the GSA algorithm and using differential grouping as a proper grouping strategy. In this approach, the maximum number of cycles in which optimization is applied to subgroups is considered to be 20 and tested on functions with 30, 500, and 1000 dimensions. Since the original GSA algorithm was only investigated when applied to functions with up to 30 dimensions, a comparison of the suggested GSA algorithm with the original GSA shows that this algorithm achieved promising results in functions with 30 dimensions compared with the original GSA. This algorithm was tested on functions with 500 and 1000 dimensions as well, and the results have shown that it performed well on these dimensions. As can be deduced from the convergence process of figures and the obtained optimal value, the resulting algorithm has achieved good results in most cases.
In the second approach, according to the results, this algorithm has a good performance in nonseparable functions except for F1. These functions are functions of the first group, including F1, F2, and F3. As can be concluded from the table's values, the proposed algorithm was able to achieve an almost optimal point. The maximum number of cycles, the population size (N), and the maximum number of algorithm evaluations are considered 20, 50, and 3000000, respectively. The values shown in Table 4 are obtained from 25 separate executions. As Table 4 represents, in some functions, the current algorithm had better performance compared to some of the existing algorithms, and in some other, it did not perform favoravly. The notable point is that if we consider convergence graphs, benchmark functions have shown a good convergence in most cases. As can be deduced from graphs, in most cases, the graph is decremental, and if we could increase the number of iterations, we could accomplish more optimal values. However, considering that these functions are large scale, this is time-consuming and requires a high-speed, powerful computation system. It is highly probable that such a system improves the answers.
In addition, the suggested algorithm had a better performance in function F2 compared with algorithms DECC-DG, DECC-D, and DECC-DML. Since F2 is a separable function, the proposed method had quite good results for the separable functions. In function F3, which is also a separable function, our method performed better than algorithms MLCC and DECC-D. Moreover, in function F10, which is a partial seperable function, it had a better performance than DECC-D and DECC-DML. The proposed method achieved better results than all other available algorithms except EADE in function F15, which is a function with 20 non-separable subcomponents. The proposed algorithm performed better than MLCC , DECC-D and EADE in function F16, which is a function with 20 non-separable subcomponents and it has shown better results than DECC-D in F19.

5-Conclusion
The Swarm intelligence algorithms were successful in solving most of the optimization problems. However, these algorithms faced the curse of dimensionality when confronting high dimension problems, which weakened their performance. One of the most popular methods proposed to solve large scale problems is using the cooperative-coevolutionary (CC) methods inspired by the divide and conquer approach. In this approach, the problem space is broken into subcomponents, each of which is optimized separately using an EA. Thus, instead of dealing with a vast space, we have subspaces with smaller dimensions that are much easier to optimize as compared with the original problem. The most important factor in the CC method is choosing the proper decomposition method with the highest accuracy percentage in placing the interacting variables in subgroups. One of the best grouping methods with the highest accuracy is the differential grouping method. In the suggested method in this paper, a problem with high dimensions is broken down into subcomponents, and a GSA optimizer algorithm is applied to each one. The proposed method was examined with two approaches. In the first approach, there was a tangible improvement in results for all benchmark functions, and in the second one, the performance of some functions has improved.