This paper proposes a case-based reasoning methodology to automatically choose the most appropriate optimization algorithms and respective parameterizations to solve the problem of optimal resource scheduling in smart energy grids. The optimal resource scheduling is, however, a heavy computation problem, which deals with a large number of variables. Moreover, depending on the time horizon of this optimization, fast response times are usually required, which makes it impossible to apply traditional exact optimization methods. For this reason, the application of metaheuristic methods is the natural solution, providing near-optimal solutions in a much faster execution time. Choosing which optimization approaches to apply in each time is the focus of this work, considering the requirements for each problem and the information of previous executions. A case-based reasoning methodology is proposed, considering previous cases of execution of different optimization approaches for different problems. A fuzzy logic approach is used to adapt the solutions considering the balance between execution time and quality of results 1 1This work has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 641794 (project DREAM-GO) and a grant agreement No 703689 (project ADAPT); and from FEDER Funds through COMPETE program and from National Funds through FCT under the project UID/EEA/00760/2013
One of the main objectives of computational intelligence is to impart systems with the ability to reproduce human-like reasoning. Case-based Reasoning (CBR) is an Artificial Intelligence (AI) approach to learning and problem solving based on the past experience, which is usually stored in a case-base (CB) [1]. CBR also captures new knowledge, making it immediately available for solving new problems. AI techniques have excelled in problem-solving as a good solution over conventional techniques.
CBR has been used in many application domains, one of them being in solving power and energy systems. In [2] a CBR system for building energy prediction is proposed, with the aim at identifying operation issues and proposing better operating strategies. Simplified models based on CBR to predict the hourly electricity consumption of an institutional building are proposed in [3]. A CBR method providing online decision-making for optimization of coal-blend combustion was investigated in [4]. The estimation of the energy performance of new buildings using CBR is studied in [5]. These are relevant contributions that cover some problems in the energy domain. However, many urgently needed issues in this area are still not addressed, such as the energy resource operation and planning.
The Optimal Resource Scheduling (ORS) problem, however, requires extremely heavy computational models, depending on the amount and diversity of the considered resources, and on the depth of network validation and analysis. For this reason deterministic approaches are, most of the times, inadequate [6]. Metaheuristics are proving to be the most suitable alternative, since they are able to reach near-optimal solutions in much faster execution times [7]. These algorithms do not guarantee the optimum global solution, but in turn the response time is much lower compared to the traditional exact algorithms that guarantee it. Many of these methods have also been applied in the resolution of the ORS problem [6, 8].
The question remains, however, on how to make most use of the whole set of available algorithms, depending on the needs and characteristics of each problem. Metaheuristic methods are able to provide approximate solutions in fast execution times, while deterministic approaches need larger times to compute, but are able to provide the optimal solution. Some work has already been made with the application of CBR systems to similar problems, namely in [9], which presents a study to try finding the ideal parameters to apply in evolutionary algorithms. In this work a CBR methodology is used to estimate the best parameter setting for maximizing the performance of evolutionary algorithms. However, in the present work authors propose, not only to adapt the parameterization of a certain algorithm to meet the requirements of execution time versus quality of results, but also to choose the most appropriate algorithm and respective parameterization taking into account the availability of several distinct algorithms of different natures.
This paper thus proposes a CBR based approach that, given the problem characteristics and requirements, and considering an historic CB log of past executions of each algorithm to solve the energy resource optimization problem with different settings, suggests the most appropriate algorithm to apply and the respective parameterization. A problem-driven approach is applied in the retrieve and revise phases, considering the specificities of the different considered variables, and a fuzzy logic based approach [10, 11] is used in the revise phase to adapt the solutions to the requirements of the new problem, namely considering the balance between execution time and quality of results.
After this introductory section, section 2 describes the CBR approach proposed in this paper. Section 3 presents the experimental findings of the application of the proposed approach to a historic CB log of previous executions done by the authors’ research team. Finally, section 4 presents the most relevant conclusions of this work.
Once the quality of the solutions (type B) of the similar cases (type A) is assessed, a decision is made on which methods and respective parameterizations are the most adequate (using the type C parameters). The Algorithm parameter is the name of the algorithm used to solve the case study. Parameters contains the parameters used in each algorithm to solve the historic case, as can be seen in Table 1. These two last parameters are type C, because they contain the information on which algorithm and parameters were used to solve the problem. After describing the content of each parameter in the historic cases, the different phases of CBR system is describe in following steps. 2.1
Analyse the A1 parameters for selecting the cases containing the same type of problem (ORS problem) and type of function (ORS function). Each historic case is filtered according to the value of the ORS problem parameter, given by equation (1). 0 , }; = {
ℎ , ( 1( )) = ( 1( )) for the ORS function, by equation (2).
Where, F1HC contains the historic cases that were filtered by equation (1). The terms HC and CS correspond to the historic case and current case study, respectively. The index j refers to the ID of each historic case, while index i corresponds to ORS problem parameter. NHC refers to the total number of historic case studies in the database.
Then, the historic cases filtered as (F1HC) are also filtered if they have the same value 2 = { 1
( ), 1
Where, F2HC contains the historic cases that were filtered by equation (2), and index i corresponds to ORS function parameter. NFH1C corresponds to the total number of historic cases filtered in (1). The historic cases with ORS problem equal to 2 (multiobjective problems) that have ORS function equal to 2, 3 or 4, i.e. minimizing the cost and other competitive objective, are all considered for a current case study with the same ORS problem and containing the same information for the ORS function parameter (2, 3 or 4). The idea with this condition is to separate problems with distinct objective function.
Determine the cases that are similar to the current one through the use of A2 parameters. For each historic case (F2HC(j)) the similarity percentage of each A2 parameter (PAH2C((ij))) is calculated by equation (3).
2(( )) = 2 { 2 ( )( 2( )) , , 2 ∀ ∈ {1, … , 2}; ∀ ∈ {1, … , 2} ( 2( )) ≥ 2
( )( 2( )) ( )( 2( )) ≥ ( 2( )) (1) (2) (3) where, NFH2C is equal to the number of historic cases filtered in previous step by equation (2), while NA2 corresponds to the total number of A2 parameters. The similarity percentage is calculated by dividing the value of each A2 parameter (A2(i)) between the historic and current cases (or vice versa - allowing avoiding similarities over than 100%). Then, the average similarity is determined, which corresponds to the similarity percentage of each historic case, and is given by equation (4)
For a current case with parameters (e.g. Period, Bus or EVs) very close to a historic one, the similarity percentage of each historic case j (PHC(j)) will tend to 100%. Finally, filter the historic cases with a similarity percentage (PHC(j)) higher or equal to 75%.
Where, set SCj contains all the similar cases.
= { 2 ( ), ( ) ≥ 0.75 ∀ ∀ ∈ {1, … ,
Met refers to the set of all similar cases that were solved by the same the total number of algorithms with different parameterization in (6). algorithm and parameterization with index Met. NSMCet contains the number of similar cases solved by the same algorithm and parameterization with index Met. NMet refers to
Finally, the average objective function (type B parameter) of all cases solved by the same algorithm and parameterization is also calculated using the previous equation (7). These values are stored in variable FunMet. Before applying this equation, the objective function values are normalized, because the cases can have objective function values 2.2
Extract the algorithms that are used in the similar historic cases and their quality parameters (type B of Table 1). The same algorithms with different parameters can be considered multiple times, if it is used in multiple similar cases. Steps 3, 4 and 5 are only applied if there is any similar historic case study, otherwise, the CBR systems will select all the algorithms that can solve the chosen ORS problem.
First, filter the algorithms with different parameterization that were used to solve the similar cases, as described in equation (6).
ℎ
= ( ( )) with different magnitudes. The number of considered historical cases is crucial, because with many cases this process can become heavy and slow, so a good historical cases selection (retain phase) is important.
Choose the most appropriate algorithms to solve the current case study through the use of a fuzzy method. The variables TimeMet and FunMet, determined in previous step, are used by the fuzzy method. First, create the membership function ( ) related to time (efficiency), which is represented in Fig. 1.
Fig. 1. Membership function of efficiency
The membership function has dynamic intervals to be adapted to every case study. The membership function starts at the minimum Time among all methods equation (7) , the second value of this function is the maximum time defined by the VPP in the input data, which is represented as MaxTime. The maximum Time occupies the other extreme of the membership function. The remaining values (y3, y4, y5, y6 and y7) are proportionally distributed between the MaxTime and the maximum time. The TimeMet equation (7) of each method Met is classified based on this membership function, which indicates how much far the Time is from the MaxTime (i.e. NEGATIVE, VERY SMALL, SMALL, MEDIUM, BIG or VERY BIG).
Secondly, the membership function (μFun) related with objective function (effectiveness), is created, which is represented in Fig. 2. from the minimum Fun. equation (8).
ℎ = {
membership function, which also indicates how far the FunMet of each method Met is Then, select the algorithms considering the and μFun classifications by ; ; } } (8) ℎ effectiveness classification (μFun). The other methods with a time slightly higher than MaxTime, which have VERY SMALL and SMALL efficiency classification ( ), are accepted if they also have an objective function close to the minimum, which are VERY SMALL and SMALL classifications for the effectiveness membership function (μFun). All methods that are classified as bigger are automatically excluded, since their execution time is too big to useful for the considered problem or the results quality is too low (big difference from the best methods).
Finally, the fuzzy confusion matrix, which joins the two membership functions (
and μFun), is applied to take actions regarding the methods with VERY SMALL and SMALL classifications. Basically, these methods are changed in terms of their parameterization to reach a lower execution. The amount of these changes will be given by the fuzzy confusion matrix, which can be consulted in the fuzzy confusion matrix presented in Table 2. This enables to consider methods that would be excluded because they are above MaxTime, but have good objective function results. of historic cases. Determine the similarity of the current case study (PCS) by applying the equations (4) and (5), include the current case in the database of historic cases, if its similarity percentage is lower or equal to 95%, defined as equation (9).
A current case with a percentage higher than 95% is not adding new value to the historic cases, since it is only bringing useless information to the processed. 0, ,
SMALL
Small reduction Very small reduction Very small reduction Very small reduction Very small reduction Very small reduction Excluded
Excluded
This paper presented a CBR methodology to support the choice of the methods to use in solving the energy ORS problem. The proposed method includes a fuzzy based process to determine the changes in parameterization that should be applied to each method that is considered promising to solve a new case with specific characteristics. It is clear that this method brings advantages when compared to a manual process, because choosing manually hardens the effectiveness of the choice, and the time spent, e.g. in the choice of parameters.
The performance of CBR systems is highly correlated with the number of cases that it imbues. Even so, the presented results suggest as final result a considerable number of methods to solve the problem, all of which with expected small execution times and good quality of results for the envisaged problem. This means that the presented methodology was effective in the selection and classification of the methods. The modifications to be performed in the methods, as result from the fuzzy process, enlarge the scope of possible methods to be applied, as rather than excluding such methods for being just a bit slower or presenting a bit worst quality of results than other methods, it still considers the most promising ones as possible solutions, subject to a degree of changes that would make them suitable to solve the problem as well.
As future work, it is intended to develop a method for deciding which parameters to modify to obtain the given value of maximum execution time, according to the results of the fuzzy process. It is also proposed to apply decision trees in the process of retrieve. Finally, the process of reviewing can be enhanced with the help of an expert, in order to build an expert system to perform the revision of the changed parameters. 11.