Sergi Canyameres

Doina Logofătu
email: logofatu@fb2.fh-frankfurt.de

Platform for Simulation and Improvement of Swarm Behavior in Changing Environments

Simulation of particle movement plays an important role when understanding the behavior of natural entities, which can be adopted by many other research fields. The complexity of every environment can cause lots of difficulties to ensure accurate und faithful results, leading to extensive researches but always in very specific conditions. This paper describes a framework which allows wide flexibility on the moving algorithms of the swarm particles as well as an easy modification of the surrounding constrictions. A simple, intuitive interface is implemented and a swarm paradigm is already used. The aim of this tool is to obtain acceptable results in any upcoming test case without the need to run an exhaustive and expensive research.

Introduction and Motivation

This paper explains the natural extension of our previous participation in the InformatiCUP challenge [START_REF]InformatiCUP[END_REF], a German competition arranged by the "Gesellschaft für Informatik" [2], an organization promoting the transmission of computer science knowledge and research. The goal in this 2014 edition [3] was to implement an ideal simulation of how a set of manganese-collecting machines had to move above a water surface without remote help on how to determine the other's position and direction. Only a small area is reached by radar that provides them information about the relative position of the nearest bots within this range. Although the purpose was to collect as much manganese as possible, the heuristics to determine which factors were to be taken into consideration were not clear. This brought to different paradigm possibilities to develop, and made us think of the need of a general purpose application instead of the strictly constricted projects existing so far. Hence, after focusing on the idea of allowing changing specific requirements, we started to work on the versatile framework that is presented in this paper. This paper is the basis of a platform which breaks the tendency of thoroughly focusing on carefully fixed environments as done so far [START_REF] Fernandes | Controlling the Parameters of the Particle Swarm Optimization with a Self-Organized Criticality Model[END_REF][5] [START_REF] Mcnabb | The Apiary Topology: Emergent Behavior in Communities of Particle Swarms[END_REF]. Here several solutions for different contexts related to the mentioned contest are purposed, even though any other cases are meant to be adopted. The robots can start in several formations, which may be a key fact when determining the movement patterns to be followed. Afterwards they start to recalculate their velocity and direction following one of the most extended swarm paradigms, studied by C. W. Reynolds [START_REF] Reynolds | Flocks, herds, and schools: A distributed behavioral model[END_REF] and consisting of three main rules. During the simulation any algorithm may be activated or deactivated as well as have their inner parameters modified. Different final events can be handled to conclude the simulation in different ways depending on previously established criteria. In many occasions it is necessary to know a first approach of the simulation's results, even when the first drafts are not yet designed. For new research fields, gaming industry or any nature-inspired applications it can be interesting to have a tool to find good preview results for simulation and optimization in a dynamic and low cost system without the need to build full applications for that purpose. Many improvements and complements are likely to be developed in the near future, such as distributed computing, more accurate methods for the optimization of the parameters, real-time comparison between two simulations, etc. Section 2 thoroughly describes the implementation of the main blocks of the application, from the structure of the program until the function to search for the best parameters. Section 3 proposes the possibility of the further parallelization of the optimization function. In section 4 we show and explain some of the first results. Finally, an evaluation of the work done as well as a brief proposal for future research can be found in section 5.

Simulation and Optimization Functionalities

Each one of our units is an instance thinking independently and interacting with the simulator class just enough to represent real-life perception of the individual. A coordinate's class is implemented in such a way that all position-and velocity-related data is embedded and can be easily transferred and recalculated. The central processing class organizes the tasks and handles the list of robots, coordinates, parameters and rules to follow, but are the single instances the responsible for taking their own decisions with the limited information provided. The surface where the robots are going to move should be unlimited, but for a comfortable visualization in the GUI this area is constricted to a canvas of 500 by 500 positions or pixels (in this case, representing square meters).

Deployments

The starting positions of the robots determine the first decisions to take and may condition the overall algorithms to follow. If they start very close to each other, they need to spread in order to cover more area. On the other hand, if they are too distant, many areas may remain uncovered or clearing them would be too inefficient. In the contest, the initial methodology to distribute the robots was never specified and each simulation uses a different starting set. Therefore, it is important to have the chance to test a same moving paradigm after different deployments. For this, five starting configurations are now implemented, following different regular patterns (square, circular) or mathematic distributions (random, Gaussian and double Gaussian).

The Random (Fig. 1.5) deployment drops every robot in a completely random position within the sea limits established in order to focus the simulation in a constricted area. In further simulations much larger limits may be used, taking the risk of dropping robots too far away from the rest and becoming isolated. An interesting line of research could study which algorithms should isolated robots follow. However, a purely random starting set does not bring many possibilities to study constricted behaviors, so more complex irregular deployments are developed.

The Gaussian (Fig. 1.1) and Double Gaussian (Fig. 1.3) configurations are used to guarantee a certain pattern within the randomness of a non-uniform distribution. With them we can know a priori how are the robots going to be distributed, even not their exact coordinates or the distance between them. Obviously, parameters such as the deviation can be manipulated in the every simulating case. In the case of the Double Gaussian, this is the name that an evolved deployment received. It consists of two Gaussian deployments, which are independent on number of items and deviation. Both means are calculated in a way that some robots from one kernel can perceive some of the other one, but never all of them. With this, we try to see the strength limits of the algorithms, as both Gaussians will tend to merge and join their own nucleus but at the same time some robots may push towards the other group.

Finally, regular patterns are also implemented to test uniform movements or simulate situations where the initial set can be regular. In this first version, uniformly fulfilled Square (Fig. 1.2) and a Circular (Fig. 1.4) patterns are available. Due to the variable amount of bots, the shape might slightly vary to try to keep the regularity of the distribution. The square will become a rectangle to ensure equal distance between all the boids, whereas the circle will deploy equally-distant robots on the circumference until this is full and a new ring can be added.

Swarm Behavior: Equations and Weights

The limited communication capacity between the robots makes it too complex to determine the shape or the positions of all the other robots (a strong communicating network should be established) and it would escape from realistic situations. Natureinspired algorithms for ants [START_REF] Moyson | The collective behavior of Ants : an Example of Self-Organization in Massive Parallelism[END_REF] or bees [START_REF] Rodriguez | An Artificial Bee Colony Algorithm for the Unrelated Parallel Machines Scheduling Problem[END_REF] are not based on sharing such big amount of data, but on generating a collective behavior out of the minor parts of information shared by each individual [START_REF] Tereshko | Collective Decision-Making in Honey Bee Foraging Dynamics[END_REF].

The moving paradigm chosen always follows a same overall concept [Fig. 2] [START_REF] Reynolds | Flocks, herds, and schools: A distributed behavioral model[END_REF] but at the same time we introduced some regulators which make the decisions experience small variations in order to adapt to the specific situation of each individual within the group. Every single robot analyzes the relative position p i of all its n surrounding bots and calculates a variation of speed and direction after a weighted average of the values obtained through the main following rules:

   n i iy ix p p n n g surroundin 1 ) , ( 1 ) 1... ( cohesion (1)
Formula (1) calculates the average position of the nearby robots and tends to move there to follow the principle of cohesion and avoid the group spreading around or a robot to travel too far away, which may result in losing contact due to its limited view. After testing, this basic concept was not acting enough as a real-like flow, so a small correction was made to empower the weight of this algorithm when the boid is very far away from the others, and to decrease it when it is too close. To avoid direct contact between the elements, the separation algorithm (2) is also introduced in the final calculation of the new movement.

In this case, the algorithm finds the opposite value of the cohesion formula. However, only when the object is very close to the others is when this algorithm should be more important. For this reason, the average point is calculated among the robots positioned in a smaller range than the viewing area used normally. In a similar way as in the first algorithm, this final value is not proportional with distance and gets strongly increased when the robot is too close to others, so it would avoid a final crashing between boids. Finally, a third formula (3) computes the average direction where the neighboring robots are moving to. This alignment offers a smoother and more realistic movement and provides a non-static understanding of the environment, as it uses the actual velocity instead of the positions.

   n i iy ix v v n n velocities lignment 1 ) , ( 1 ) 1... ( a (3)
The modularity of these implementations allows a full addition or modification of the algorithms to follow. During each iteration of the simulator, which could be understood as a second or as any other time unit, all the robots obtain the list of neighboring boids as well as the algorithms to handle. With this, they decide which algorithms and with weights use, independently from the simulator class. Only once they all have finished the calculation of their decision, is when the actual movement takes place. This avoids that the last robots in the list take decisions with later information about already updated positions, which would not be realistic and may cause synchronization problems as well as the possibility of looped situations. described by Craig W. Reynolds [START_REF] Reynolds | Flocks, herds, and schools: A distributed behavioral model[END_REF].

After the calculation of the final movement, a limiter controls an excessive value of the speed and reduces it to a established maximum, which can be common for all boids or specified for each individual.

Bigger dynamic paradigm modifications are also necessary for the proper simulation of realistic environments. Although the (1) and (2) criteria have small variations for specific situations, sometimes these are not enough and a new value for the algorithm's weight or even a completely new behavior must be done. In this version of the application, a practical modification of the weights allows the creation of the Recollection command, which consists on make all the robots meet in a central point.

The original instructions from the challenge asked the boids to be collected at a certain point by a mother ship. In any case, the goal was to make them gather, even no optimization method was asked again. A good choice would be to reduce this time to the minimum by meeting them in the central point between the extreme boids. However, our choice was to optimize the fuel consumption so the parameter minimized was the total track covered by all the robots until they reach this point. For this, a signal can command the separation (2) and alignment (3) weights to become 0, so the full decision of the movement relies on the cohesion algorithm (1) and the boids are set to move at full speed. This is represents a realistic situation where the robots are called from the central control of the mother ship, or, with a set of timers, they have the command to gather at a certain execution moment, or after a threshold of inactivity due to the balance of all the robots when they are all close to each other.

Optimization Function

The aim of this research is to develop a tool which offers different possibilities of simulation, measurement, understanding and comparison, but maybe the most interesting utility is the optimization module. This function can still be improved by using more sophisticated methods such as gradient ascents, neural networks, etc. but the current version already offers a good approximation of the best parameters to use in order to reach a specified goal. Manganese collected, total or unique track covered or time to gather could be some of the goals in our goal to continue with the InformatiCUP context. The goal pursued in all the tests shown in section 4 is the total amount of manganese collected by all the robots combined.

The idea is very simple and it consists on testing a specific configuration until the robots reach a balanced position, or if not, until they reach a time or distance travelled limit (as if it was fuel). The simulation accepts the introduction of a set of values chosen by the user to test, if some previous stipulation has been done because those parameters are more likely to be good. With small variations, the iteration can skip useless values as well as reduce the step between them when testing. Despite of having different starting sets, the current version asks for a fixed deployment to test with, as they are considered fully different experiments in separate contexts. Many different amounts of robots, instead, can be added in the iteration system and different weights can be tested on different number of robots for the given deployment method.

In case of choosing non-uniform deployments, the positions of the robots are calculated once and saved for further simulations, in order to guarantee that the results correspond to equal testing conditions.

At the end of each simulation a .txt is generated with a header indicating which range of configurations was used, tested number of robots, and the values which offer the best result obtained. With the purpose of a better understanding of the behavior seen during the variation of the values, a list of all the iterations and the desired results for each combination is now included. A Matlab script processes these outputs and prints a 3D representation of the results, which would be too complex to understand without data processing to summarize them. This graphic can only use two of the parameters simultaneously, as the third axe is always representing the target value. Fortunately, the algorithms used so far are conceptually easy so it is possible to understand the results with the use of two graphs. Further applications will need new solutions for the improvement of these graphs and the output interpretation, but it depends on the algorithms used so no further preparation could be done now.

Parallel Computing with MapReduce

The longest simulations iterating over all the parameters can run for some minutes, in the most complex cases with small steps between iterations and a high number of robots, even almost an hour when using a 2GHz i5 laptop. Future applications may need more constrictions, new algorithms and even higher number of individuals, so the computation time can increase exponentially. To ensure an acceptable simulation time it is going to be essential to focus on a big improvement in this aspect.

The number of shared data and parallel applications worldwide is increasing very fast, so we would like to use some of these techniques as a solution to the excessive computation time.

Apache offers an open-source implementation of the MapReduce [START_REF] Dean | MapReduce: simplified data processing on large clusters[END_REF] called Hadoop [START_REF]Apache Hadoop open-source implementation[END_REF]. MapReduce splits the input in the map tasks so the data can be processed in different cores simultaneously. Afterwards, the Reduce tasks collects all the partial results, sorts them and, in our case, search the best configuration among all the simulations run. This model is a good candidate to be implemented in this kind of projects, as has already been done in similar applications [START_REF] Logofătu | Parallel Evolutionary Approach of Compaction Problem Using MapReduce[END_REF].

First Experimental Results

The application was first tested by executing simple, understandable parameters with uniform deployments, to see how the system behaved. Balance was easily reached with circular deployment and equal cohesion (1) and separation (2) weights. Once the testing phase proved the correct performance of the simulations through the GUI interface, the first full executions were done.

As explained previously, the need for variations in the algorithms as well as the more detailed output was solved, and finally some applicable results were obtained and shown (Fig. 4) with the Matlab script described in Section 2.3. The results obtained so far show a logical evolution of the manganese recollection. If the separation value (w2) is too small or too big, the movement is affected in excess, due to the variations implemented which empower its value when a robot is too close to the others. On the other hand, the similarity of the two graphics for cohesion (w1) or alignment (w3) suggest that these two algorithms are less decisive in comparison with the separation one. This makes the further work focus on the study of a better weight balance for this specific situation. However, the purpose of this first use of the framework is to observe and analyze its possibilities, which we consider successful. The algorithms used work properly and the graphical results are encouraging.

Conclusions Future Work

Being satisfied with the performance of the platform, our next research will focus mostly on the improvement of the general behavior of the simulations, looking for a more efficient execution. The implementation of new functionalities is imminent, for example the possibility of run two different simulations (with different number of robots, deployment method and/or algorithms) at the same time using the visual interface. This can help to visually compare two behaviors at real time, hopefully avoiding the need of result post-processing. Last but not least, as a mid-long term task to do, the parallelization method explained in section 3 to ensure acceptable execution times with larger and demanding simulations.

Fig. 1 .

 1 Fig. 1. Captions of the robots with the GUI representation of the different deployment methods: Random (1), Square (2), Gaussian (3), Circular (4) and double Gaussian (5).

Fig. 2 .

 2 Fig. 2. Visual representation of the principles of cohesion (1), separation (2) and alignment (3) described by Craig W. Reynolds [7].

Fig. 3 .

 3 Fig. 3. Scheme and general pseudo code for one of the next steps in this project, the parallel computation of the simulation. Both diagram and code show how the Map splits all the configurations' processes into different chunks which are separately calculated and reunited by the Reduce to find the best result.

Fig. 4 .

 4 Fig. 4. Two graphics showing the total Manganese obtained (vertical axe) depending on the parameters of cohesion (w1) and separation (w2) on the left, and alignment (w3) and separation (w2) on the right. Both cases have an irregularity at the beginning of the performance.


Jacek Mańdziuk
email: j.mandziuk@mini.pw.edu.pl

Aleksandra Woźniczko

Marcin Goss

A neuro-memetic system for music composing

For thousands of years music has accompanied human existence and development. Over the time it turned into a form of art capable of expressing beauty, ideals and emotions. Our previous work has investigated the possibility of automatic generation of music that would be (to some extent) alike to the music created by human composers. Our focus was on romantic era music, in particular a "Chopin-style" compositions. We have proposed a specifically designed memetic algorithm, which operated based on a handful of parameters and rules, which need to be followed when it comes to classical music. In this paper we review the proposed approach and extend it by introducing "a subjective factor" to the system, in the form of a specifically designed neural network. The role of this component is to provide the subjective preferences of the listener, which are taken into account during the music composition process. Preliminary results of this new system are presented.

Introduction

The topic of music creation has been of research interest for about 30 years. One of the earliest experiments was the soundtrack to a game called "Ballblazer" generated algorithmically in 1984. The lead melody was assembled from a predefined set of 32 eight-note melody fragments or riffs, which were put together in a random manner. The system had to make several parameter-based choices including the speed and loudness of playing, omitting or eliding notes, or inserting a rhythmic break. The melody was accompanied by bassline, drums and chords, which were also assembled on the fly by a simplified version of the above approach. In effect the music was played forever, without repeating itself, and not straying too far from the original theme [START_REF] Langston | Six Techniques for Algorithmic Music Composition, 15th International Computer Music Conference[END_REF], [START_REF] Langston | 2332 or Eedie & Eddie on the Wire, An Experiment in Music Generation[END_REF].

Another interesting example is an interactive music system called iM U SE created in 1990 and used in a number of video games. The system is able to "adjust" or "synchronize" the composed music to the game's action and to make transitions from one musical theme to another [START_REF] Smith | Rogue Leaders: The Story of LucasArts[END_REF]. Probably the most similar system to our goal is "Emily Howell" -a computer program with an interactive interface that allows both musical and language communication. The system can be "taught" to compose music more fitting an operator's taste in the process of "encouraging and discouraging". The program uses musical pieces, previously invented by another composing program called Experiments in Musical Intelligence (EMI), as a source database for its musical choices [START_REF] Cope | Experiments in Musical Intelligence[END_REF], [START_REF] Cope | The Algorithmic Composer[END_REF].

More recent examples of the systems capable of or supporting artificial music composing include ArtSong [START_REF]Algorithmic Composition Software -ArtSong[END_REF], Symbolic Composer [START_REF]Symbolic Composer[END_REF]Cybermozart [8] or Lexikon-Sonate [START_REF] Essl | Lexikon-Sonate[END_REF].

The above-mentioned examples inspired us to develop a system capable of creating pieces of music to some extent similar to those composed by humans and at the same time being able to take into account individual musical preferences of the operator.

The rest of the paper is organized as follows. In the next section we summarize our memetic approach to automatic music creation [START_REF] Mańdziuk | Chopin or not? A memetic approach to music composition[END_REF] along with a selective introduction to the theory of music. Section 3 details the role and significance of the neural network component added to the system. Conclusions and directions for possible expansion of this research are placed in the last section.

A memetic approach to music composing

The term music has too broad scope to be effectively covered in a single approach. Hence, for the sake of tractability, we decided to restrict our research to the romantic era, as music created at that time was still following classical rules, but at the same time, the harmony was not evident. Additionally, we decided to compose pieces for the piano as this reflects the expertise of one of the authors.

Our goal was to create a system that would compose a regular piece of classical music based on user's input. In particular, we aimed at verifying the two following aspects: whether the musical rules and regularities could be flexibly applied and whether it is possible to reflect an individual taste in composed pieces.

Our studies referred to three piano music forms popular in the romantic period, i.e. nocturne, polonaise and mazurka. In particular our focus was on the compositions of Fryderyk Chopin, who wrote many such pieces.

The structure of composed pieces / keys / repetitions

In order to reflect the rules of music composition and structure of musical pieces we distinguished the following elements (listed in a descending order): a part, a period, a sentence, a phrase, and a motive. Each of these elements (except for motives) is divided into several other smaller elements (see Fig. 1). Each motive consists of two separate lines which are a melody and an accompaniment.

Another important part of the theory of music are keys [START_REF] Benade | Horns, Strings, and Harmony[END_REF], [START_REF] Kostka | Tonal Harmony[END_REF]. Each part of a piece has its base key, but it is possible that the key changes into a temporary key, which may be different from the base key. For each of the keys there are four other related keys: same name key, parallel key, subdominant key and dominant key (see [START_REF] Mańdziuk | Chopin or not? A memetic approach to music composition[END_REF] for a detailed explanation). Another crucial aspect of classical music are repetitions. This issue is addressed by creating a repetition matrix defining the probability of repeating each base element within the part as well as between parts. Based on the theory of music different probability schemes were implemented for nocturne, mazurka and polonaise, respectively (see Table 1). In the table m, h, s and p denote motive, phrase, sequence and part, respectively. The row marked with a black square defines the probability of repeating a given element in the same part (e.g. s = 0.55 in column A means that on average any sentence in part A is repeated with probability 0.55). The remaining rows define probabilities of choosing a particular part as a source one (for an elements' repetition). For instance, m = 0.2 in row B and column C denotes the probability of repeating the a motive form part B in part C. The first column denotes the respective repetition probabilities in parts A * , B * and C * , respectively, i.e. the parts which represent "variations" of the original parts. Based on the theory of music the following schemes were implemented: ABA for nocturne, ABA * for mazurka and ABACA for polonaise.

Table 1. One of the repetition matrices used in the experiment. See description within the text.

[]* A B
randomly, but changes it according to a set of predefined rules that represent domain knowledge. After a pre-defined number of algorithm's generations the system yields a specimen that represents a musical piece with the highest fitness value. The algorithm receives a set of parameters as its input, part of which is a set of standard parameters of the evolutionary algorithm and the other part results from the plug-in architecture of the fitness function and local optimization. These parameters are set directly by the user and include: the number of specimens in the population, the number of generations, the percentage of the elitist specimens (transferred to the next generation without mutation), the probability of performing local optimization, the weights of particular components of the fitness function, as well as, parameters responsible for mutation (its range, probability of notes modifications, probability of chords modifications, and permutation range).

Furthermore, the algorithm uses parameters which reflect the rules of composing homophonic music: the key graph, probabilities of occurrence of particular chords in a particular key and probabilities of occurrence of particular notes in particular chords in particular keys. The final set of parameters describes the musical form, like possible structures of the piece, its meter, textures and repetition matrix.

Generation of a population

The process of primary specimens generation is analogous to the base methods of (traditional) music composing, i.e. first harmonic structure of the piece is created and then it is filled with particular notes. The initial population consists of some pre-defined number N of specimens generated pairwise independently. In this phase of the algorithm musical rules and form parameters are exploited most intensively.

Generation of a single specimen is quite a complicated process and consists of numerous steps, as shown in [START_REF] Mańdziuk | Chopin or not? A memetic approach to music composition[END_REF]. On a general note, first, the biggest elements (parts and periods) of a piece are generated, followed by the smaller ones (sentences, phrases and motives).

Memetic (local) optimization

The goal of local optimization is to improve the quality of a specimen from musical theory point of view. Having in mind that some amount of "randomness" seems to be beneficial in artificial music composing, local optimization may happen in each generation but with some probability defined as one of the input parameters.

The first local optimization consists in adding a pitch to the existing chord which is the sixth or the seventh step of the chord's key. This operation is based on an extended version of a database of chains of chords with three or four elements used in Harmonia educational tool [START_REF] Kwong | National Institute of Education in Singapore[END_REF]. It includes chains of possible chords together with their possible modifications. If a particular chain is present in the database, it is then modified accordingly.

The second optimization operation is focused on technical ability to play the composed piece (i.e. the scale and chords location can be modified, if necessary, so as to actually allow playing the piece with two hands of a pianist).

The third operation allows improving the chords played on either a melody or an accompaniment so as there are more consonants (concords nice to hear) than dissonances (concords strange to hear). The last local improvement operation provides a way to minimize the number of pauses appearing in the musical piece. As pauses, in general, are in line with musical rules, they are usually "over-represented" in the specimens.

Fitness function and selection

The selection is roulette-elite. The fitness function consists of several components which are independently evaluated and have different weights (depending on the form) configured by the user. Specifically, the following components are considered: Chains -evaluates the correctness of chains of chords using pre-defined Markov chains, Concords -evaluates concords based on the number of existing consonances and dissonances in a strike, Rhythm -evaluates the homogeneity of the rhythm in the motives, Tonalityevaluates the tonality on the main measures in the meters as high tonality should be maintained, Pitch -evaluates the homogeneity of notes' pitches in the motives.

Mutation

The degree of mutation operator depends on the parameter that sets the percentage of the motives that will be mutated. Mutation may either change the heights of particular notes or change the chords. Moreover, mutation may change the order of motives based on the mixing intensity parameter. If mutation is to change single notes, then a decision is made independently for each of them, with a pre-defined probability threshold. If so, first the origin of the new note is decided (whether it is the current chord, a key, base key or random), then a particular note is chosen. If mutation is to change chords, the procedure is similar to the one used for changing notes, but the origin may be main chord of current key, side chord of current key, main chord of another key, side chord of another key or random.

The degree of the other facet of mutation -changing the order of motives -depends on the mixing intensity parameter, which defines the percentage of motives to be reordered. First, a set of motives which will remain in the primary order is chosen. All other motives are inserted in random places between the "stable" motives in the piece.

Summary of results

The initial series of tests aimed at optimization of the steering parameters of the memetic algorithm: % of elite -percentage of the specimens with the highest fitness automatically promoted to the next generation, % of optimization -probability of the local optimization to take place in the current generation, mutation range -the percentage of motives to be mutated, notes/chords modification factor -a factor describing the relation between probabilities of mutation of notes and chords, e.g. 3/1 means 75% for notes and 25% for chords, permutation range -the percentage of motives that will remain in the primary order. Each combination of parameters was verified in 10 independent experiments with population size equal to 150. Each ensemble of 10 tests was performed three times, once per each considered form (mazurka, polonaise and nocturne).

The final selection of the algorithm's parameters was based on the average score of the best specimen evaluations across 10 populations. It turned out that for each of the tested forms different sets of parameters were the ones most effective. The best set of parameters of the mazurka form: % of elite= 1, % of optimization = 15, mutation range = 33, notes/chords modification factor = 3/1, permutation range = 25, has been chosen for further final tests, which involved three human testers.

Each of the testers received the same set of 300 pieces (of mazurka form) to listen and evaluate using the scale of -1 (worst) to 1 (best) with a step equal to 0.5. The confusion matrices for each pair of the testers are presented in Fig. 2. Generally speaking, it is easy to notice that the testers are often consistent when it comes to the pieces marked lower. This can be seen in the top left corners of the matrices. Furthermore, the testers do not always agree when it comes to the pieces rated with the highest marks which is most probably caused by differences in testers' tastes as well as a small number of the highest rated pieces in the set. A detailed analysis of results is presented in [START_REF] Mańdziuk | Chopin or not? A memetic approach to music composition[END_REF].

A neural network component

The above described system can be regarded as an "objective" mechanism for composing music according to the rules (parameters) appropriate for a given musical form.

In the current version of the system we added a neural network component, which reflects the user's taste and whose score was added to the fitness function. Neural network training is preceded by extracting style parameters from the pieces listened by the testers Fig. 3. Average values of style parameters of pieces highly evaluated by the testers (evaluations of 0.5 and 1) and pieces low evaluated (evaluations of -1 and -0.5) in comparison to averages of style parameters in the whole population.

(see Fig. 3). The analysis of these graphs allows to observe that the testers have different style parameters in the pieces they prefer. For instance, it is easy to observe that Tester 2 negatively judges pieces with low repetition rate of motives. The same pieces are evaluated higher by Tester 3 or Tester 1 positively evaluates pieces with low variance of notes height in motives, unlike Tester 2.

In the training process the input to the network consists of a set of eight style parameters, depicted in Fig. 3, extracted from the 300 evaluated pieces:

the ratio of the number of motives versus the number of unique motives the difference between the highest and the lowest note in the piece average value of the variance of the height of notes in motives average value of the variance of the height of notes in phrases average value of the variance of the rhythmic values in motives average value of the variance of the rhythmic values in phrases average ratio of unique heights of the notes versus number of notes in motives average ratio of unique heights of the notes versus number of notes in phrases The choice of parameters reflected our willingness to find such a characteristics of a piece that may take different values for various pieces and may be correlated (positively or negatively) with the individual musical taste of the listener (tester).

For each specimen (musical piece) obtained in the previous experiment, all eight parameters are extracted, normalized to < -1; 1 > and used as an input to a neural network. The hidden layer consists of four neurons and the activation function is bipolar sigmoid. The network's single output belongs to < -1; 1 > and represents the degree to which the piece reflects the listener's taste.

Neural networks (one for each tester) taught in the previous test were included in the algorithm and each of them was used to generate 50 pieces. Additionally, 50 pieces were generated with the help of previously described memetic system, with no use of a neural network.

For each of the testers, after mixing up 50 pieces generated with the use of the respective neural network and 50 ones generated without the network, the 100 pieces set was ready to use in the subsequent tests. Each set was mixed twice (the pieces were shuffled) and given to the respective tester without the labels. As a result each tester had two lists of the same pieces in different order and listened to them with no knowledge which pieces were generated using the neural network and which were not. In order to increase the credibility or the test listening to the first set was followed by a 24 hour break before the tester started to listen to the second set.

The average scores of the testers are presented in Fig. 4. For the sake of clarity it should be noted that among the three testers there were two co-authors of this paper. The third person, Tester 3, was completely unrelated with the paper and implementation of the project and may be found as the most independent source of tests data. On the other hand, due to "blind" construction of tests it was practically impossible to intentionally manipulate the results of Testers 1 and 2, thus we decided to publish them on equal rights as those of Tester 3.

The results of the performed tests may be assessed as moderately positive. Even though the evaluations are not always fully consistent, in all three cases the average evaluation of all listenings is higher for the pieces generated using the neural network. This allows us to say that using the neural network is beneficial for matching the created music to ones taste. On the other hand the observed improvement in the quality of Fig. 4. Summary of the results of "blind" test specimens is not substantial. Relatively large differences between two runs of the ex-periment performed by the same user should, to a large extent, be attributed to changing and uncertain nature of testers' (human) perception.

In summary, the results allow us to say that the approach presented in the paper is a promising idea in the area of computer music generation. The proposed memetic system is able to construct pieces imitating popular musical forms and the additional use of neural network allowed generation of the pieces statistically more attractive to the recipient. This allows to ascertain that generated musical pieces reflect some aspects of human/artificial creativity and extend beyond the formal rules and theory of music.

During the experiments a few hundreds of music pieces of various forms (polonaises, mazurkas and nocturnes) and quality were generated by the system. Some of them clearly sound "artificial" and by no means may pretend to be composed by a (non-novice) human composer. There are, however, also quite many examples of "more human-like" compositions. An example of such a piece (of the form of mazurka) in presented in figure 5.

Conclusions and directions for future work

In this work we studied two main aspects of the composed music. The first one refers to the initial stage of generating a musical piece. The hybrid algorithm allows creation of pieces, which are consistent with the user's expectations in the field of musical rules, harmonic and rhythmic restrictions, types of used textures and construction of the whole form. The fitness function evaluates the actual state of the piece and local optimization brings in the "formal order". Repeated execution of these operations allows achieving the goal of a piece containing expected musical substance. The end result is substantially dependent on the user's intentions and ability to translate theoretical knowledge into configuration of individual parameters and the input of the algorithm.

The second relevant aspect that we analyzed in the paper regards reflecting individual taste of particular listeners. Test results clearly show the influence of the use of neural network that learned from a person's preferences on the final quality of the generated piece. Thanks to this mechanism it is possible to not only generate music which fulfills the expectations related to the musical substance, rhythmics, harmonics and texture, but also reflects, to some extent, the sense of aesthetics and beauty of an individual user.

Our current focus is on deeper analysis of the factors defining user's individual preferences, which may potentially enhance the neural network's results. We also plan to perform more test involving other testers possibly with the help of social networks.

Fig. 1 .

 1 Fig. 1. Exemplary structure of a music piece.

Fig. 2 .

 2 Fig. 2. Comparison of testers' evaluations in the form of confusion matrices. For instance, value 11 in the first table means that there were 11 pieces evaluated as -1 by Testers 1 and as -0.5 by Tester 2.

Fig. 5 .

 5 Fig. 5. Example piece of the form of mazurka.

Acknowledgements

The authors would like to thank Dr Eddy Chong from NIE (Singapore) for providing them a database of chords chains that was used as part of domain knowledge representation in the local optimization phase.

Memetic algorithm

Our music composing system is based on memetic computing which is a combination of genetic algorithm and in-generation, local optimization. The local optimization phase serves as an additional mutation operator which does not mutate the specimen


Armin Ghasem Azar
email: a.ghasemazar@iasbs.ac.ir

Mansoor Davoodi

Mohsen Afsharchi
email: afsharchim@znu.ac.ir

Bahram Sadeghi Bigham

A Greedy Agent-based Resource Allocation in the Smart Electricity Markets

The smart grid makes use of two-way streams of electricity and information to constitute an automated and distributed energy delivery network. Coming up with multi-agent systems for resource allocation, chiefly comprises the design of local capabilities of single agents, and therefore, the interaction and decision-making mechanisms that make them create the best or at least an acceptable power allocation. Due to the several issues in providing sustainable and affordable power energy, researchers try to think about creating a decentralized mechanism to be able to manage the entire transactions in retail electricity markets. As a result, this electricity infrastructure is predicted to develop into a market of markets, during which all the trading agents influence on each other and have role in toward an equilibrium one. In these markets, we are interested to minimize the buyers' purchasing cost. Motivating this issue, we model the demand response problem in an evolutionary optimization framework and propose an evolutionary algorithm for handling the decentralized market-based resource allocation problem.

Introduction

Intelligent power networks, Smart Power Grids, are an enhancement of the present century and the result of experts' efforts to improve the power distribution mechanisms. Conventional power grids are mostly utilized to transmit the power from the central generators to an extensive variety of the end users. Conversely, the smart grid uses twoway streams of electricity and information to create an autonomous energy delivery network [START_REF] Fang | Smart gridthe new and improved power grid: a survey[END_REF]. Toward this issue, multi-agent systems not only represent the consequent massive steps within the development of the next generation energy delivery network systems, but they also reveal new strategies to design highly flexible ones [START_REF] Rogers | Delivering the smart grid: Challenges for autonomous agents and multi-agent systems research[END_REF]. Coming up with multi-agent systems for distributed resource allocation, chiefly comprises the design of local capabilities of the trading agents and therefore the interaction and decision-making mechanisms that let them create the best or at least an admissible allocation. One of the challenges in this context is the Demand Response problem. Due to the several issues in providing sustainable and affordable power, creating a decentralized mechanism that be able to manage the entire transactions dynamically, is an interesting problem among researchers and practitioners [START_REF] Albadi | Demand response in electricity markets: An overview[END_REF]. Proposing a comprehensive approach considering the minimization of buyers purchasing cost, where the decision process of resource allocation is expressed as a demand response optimization under certain constraints, is one of the main contributions of this paper. In this respect, the "market-based resource allocation" mechanisms are motivated by economical features [START_REF] Papavasiliou | Market-based control mechanisms for electric power demand response[END_REF], in which the resources are allotted utilizing the competition between trading agents.

In order to model such mechanisms, one of the main approaches is to create decentralized markets among trading agents [START_REF] Bichler | Research commentary-designing smart markets[END_REF]. In this approach, instead of having a dealer, to control the whole system, the environment is divided into diverse non-overlapping regions, in which there is a dealer in each of them who is responsible for controlling all the inside transactions. Motivated this idea, a comprehensive mathematical model to formalize the decentralized demand response optimization problem in the smart power markets is proposed. Taking into account the fact that buyer agents are self-interested, they are concerned with minimizing their purchasing costs. In order to satisfy the buyers demands, agents named sellers, are responsible for producing their needed power. Therefore, finding an optimal permutation of buyers to purchase their required power in the electricity markets, necessitates using evolutionary computation techniques.

So far, however, there has been little discussion about using evolutionary computation techniques for the demand response optimization problem in the smart electricity markets. Finding an optimal permutation of buyers requires calculating all the permutations. Accordingly, this problem is similar to Quadratic Assignment Problem which is a NP-Hard one [START_REF] Lawler | The quadratic assignment problem[END_REF]. Evolutionary algorithms are typically used to provide good approximate solutions to problems that cannot be solved easily using other techniques. Many optimization problems fall into this category. It may be too computationally-intensive to find an exact solution but sometimes a near-optimal solution is sufficient. In these situations evolutionary techniques can be effective [START_REF] Bäck | An overview of evolutionary algorithms for parameter optimization[END_REF].

The rest of this paper is organized as follows. Section 2 contains a review of the related work. In Section 3, we presents the comprehensive description of the mathematical system model with the proposed solution approach. Decentralized greedy resource allocation algorithms along with the evolutionary optimization techniques, definitions and tips are members of the next section. Fifth section demonstrates experimental results. Finally, conclusion and future work are drawn in the last section.

Related Work

The initial idea of designing power markets is based on a central system which controls and politicizes all the transactions and exchanges. Many studies have indicated that the presence of only one system or a central manager is a waste of energy and money [START_REF] Bichler | Research commentary-designing smart markets[END_REF][START_REF] Dewatripont | Credit and efficiency in centralized and decentralized economies[END_REF]. Furthermore, many studies have been conducted in various aspects of these markets, specially in using multi agent systems and information systems [START_REF] Bichler | Research commentary-designing smart markets[END_REF][START_REF] Lamparter | An agent-based market platform for smart grids[END_REF]. Lamparter et al. have designed an electricity market based on the intelligent agents' technologies. They have presented miscellaneous scenarios of software infrastructure based on the multi agent systems to create this type of markets. Moreover, there is a comprehensive litera-ture review on electricity market designing and interdisciplinary processes required for achieving the decentralized markets [START_REF] Bichler | Research commentary-designing smart markets[END_REF].

Besides, some of the researches in the field of the energy optimization, including those reported in [START_REF] Homchaudhuri | Market based allocation of power in smart grid[END_REF][START_REF] Homchaudhuri | A market based distributed optimization for power allocation in smart grid[END_REF], have demonstrated optimal domestic energy management via linear programming, where power required by each device in a house is optimally met by the available resources. Similar works of power matching can be found in [START_REF] Homchaudhuri | Market based allocation of power in smart grid[END_REF], in which the proposed market model is based on a centralized approach with only one manager. In this paper, HomChaudhuri et al. have used a centralized market which does not allow buyers or even sellers to have power negotiation with more than one individual. Furthermore, it is assumed that all the sellers' surplus powers are much more than the buyers' demand. Considering these parameters, the proposed market will not confront critical circumstances. In addition, behaving only in the benefit of buyers in line with the sellers' elementary price update mechanism, which depends only on the number of buyers which are desired to purchase power from them, are studied in [START_REF] Homchaudhuri | A market based distributed optimization for power allocation in smart grid[END_REF]. The proposed technique optimizes the loss rate of power distribution. Considering their demands and surpluses, matching buyers to sellers is based on the linear programming. Nonetheless, if any of the buyers cannot satisfy its demand in one interval, then, rest of that will be transferred to the next power matching intervals. Finally, in their paper, the fitness is based only on the distance among the buyers and sellers.

This paper follows a case-study design, with in-depth analysis of demand response optimization problem in electricity markets. Proposing an evolutionary greedy power matching algorithm for this concept concerning buyers' profit, is the main contribution of this paper. Besides, proposing a greedy iterative price update rule for seller agents for updating their offered prices for each unit of price in the consecutive time intervals is another contribution.

System Model

Visualizing a city with the self-healing power grid necessitates considering the multiple issues that are significant to include. Some belong to the physical infrastructure, for example the generators, transfers and transmission lines. Hereinafter, we focus on the issues in the physical infrastructure which also involve decentralized market-based resource allocation. Consider a city which is composed of a unique main power source, namely macro-station, which is connected to the main power grid of the city, along with a network of buyers and sellers. It is assumed that the macro-station is too far from the main power grid of the city and also purchasing power from this station both costs a lot and incurs high power loss during the power transfer. Furthermore, considering the macro-station is always on-line and has infinite surplus power, will assure us of having a consistent and reliable power source in critical and unpredictable circumstances. Trying to reach the purpose of having a decentralized controlling mechanism of the power exchanges among the distributed buyers and sellers, has motivated us to partition our city into regions. Each of them not only contains a non-empty subset of buyers and sellers, but a power-dealer is also allocated in order to control the power exchanges among the agents. In addition, R k is denoted as the k th region. Subsequently, the buyers and sellers sets in the k th region are represented by R B k and R S k respectively. Finally, it is assumed that the system model is studied for consecutive independent intervals, t = 1, 2, . . . , T .

Analyzing essential parameters to obtain an optimal solution in power matching of buyers and sellers, represents the substantial challenges in demand response problem [START_REF] Kirschen | Demand-side view of electricity markets[END_REF]. Therefore, a mathematical solution approach is applied toward this issue. That the markets behave only in the benefit of buyers is the markets' main perspective. Minimizing the purchasing cost in power negotiations is the buyers' main objective. In this approach, sellers announce power prices in consecutive intervals and buyers choose sellers considering prices along with other parameters.

Market Mechanism

In all the power markets, each unit of energy has a price for selling. Also, each unit in the electricity markets is in the range of (p l , p u ). p l and p u are constant and belong to minimum and maximum price of each unit of power respectively. Dealers broadcast this range prior to the start of power exchange to the sellers. Considering our market mechanism, sellers announce their own initial prices in the t th interval between (p l , p u ). Some key factors are included such as financial parameters, general attractiveness of the market and agents' risk factors [START_REF] Fang | Smart gridthe new and improved power grid: a survey[END_REF], which influence on both purposes of picking out an appropriate initial price and updating consecutive intervals' prices. Drawing out a unique parameter for all the sellers which elucidates malleability rate from the market, named δ for sellers, is essential for their mentioned purposes. In order to update the power prices in subsequent intervals, they try to alter their prices using "Iterative Price Updating" rule. For instance, if some of the sellers announce too high prices, this rule will behave in such a manner as none of them is able to have power negotiations in the next intervals. Hence, they will have to decrease their proposed prices regarding the others' prices.

In time interval t, the x t bisj ∈ Z * is represented as the number of power units which the i th buyer has purchased from the j th seller. Z * is represented as the non-negative integer set. Considering the way which this transfer is happening, there is a main transmission line in each of the regions, which all the buyers and sellers are connected to. Each of the transmission lines (τ ι k ) has a maximum capacity of power transferring which is denoted by f low τ ι k ∈ Z * . Limitation in power transfer using the distribution lines mentions that sellers cannot transfer the power more than the transmission lines' capacity [START_REF] Machowski | Power system dynamics: stability and control[END_REF].

∀τ ι k such that

∀ bi∈R B k ∀ s j ∈R S k x t bisj f low τ ι k i=1,2,3,...,N ;j=1,2,3,...,M ;t=1,2,3,...,T ;k=1,2,3,...,K (1)
Along with the confined transmission line in each region, any power exchange between a buyer and a seller is accompanied by the power loss over the distribution lines [START_REF] Fang | Smart gridthe new and improved power grid: a survey[END_REF]. This exchange is expressed by loss bisj . Both of the transmission lines' specification (i.e. maximum flow capacity and distance between the buyer and seller) have direct impact on the value of the loss bisj . For convenience, it is assumed that only the euclidean distance between a buyer and seller has impact on the power loss.

Agents' Specification

In order to explicate diverse types of the trading agents, which it is assumed to have N buyers and M sellers, following descriptions are presented as follows.

Buyers Agents who need to satisfy their demands via the sellers are known as the buyers in which the buyer b i has a predetermined demand d t bi in interval t. Thereupon:

B = {b 1 , b2, . . . , bN } (2)
Db i = d 1 bi , d 2 bi , . . . , d T bi i = 1, 2, 3, ..., N (3)
d t bi ≤ M j=1 x t bisj × 1 -loss bisj i = 1, 2, 3, ..., N ; t = 1, 2, 3, ..., T (4)
Equation ( 2) demonstrates the buyers set. Equation (3) shows the demand set of the i th buyer during all the intervals. Furthermore, d t bi ∈ Z * will be the required power unit of the i th buyer in the t th interval. Intuitively, as (4) indicates, due to power loss assumption over the distribution lines, each buyer b i should buy more than its demand in order to fulfill its requirement completely.

Sellers Agents who have Micro-Grids (e.g. solar panels or wind turbines) [START_REF] Lasseter | Microgrids. Power Engineering Society Winter Meeting[END_REF], and aim on producing power for selling, are known as sellers. Then:

S = {s 1 , s 2 , . . . , s M } (5)
Q sj = q 1 sj , q 2 sj , . . . , q T sj j = 1, 2, 3, ..., M (6)

q t sj ≥ N i=1
x t bisj j = 1, 2, 3, ..., M, t = 1, 2, 3, ..., T

Equation [START_REF] Bichler | Research commentary-designing smart markets[END_REF] shows the sellers set. Equation ( 6) demonstrates the set of surplus powers for the j th seller during all the intervals. Furthermore, the q t sj ∈ Z * is the number of the power unit that the j th seller has for selling in the t th interval. Equation [START_REF] Bäck | An overview of evolutionary algorithms for parameter optimization[END_REF] mentions that the sellers cannot sell more than their surplus powers in the j th interval.

Iterative Price Updating Rule

Designing a greedy and dominant rule for updating the sellers' prices, has encouraged us to propose an iterative price updating rule. ps t j ∈ Z * demonstrates the j th seller's surplus power price in the t th interval. Consecutively, the δs j explains the malleability rate of the j th seller from the market as mentioned in the previous section. Sellers learn from not only their previous prices, but also the other sellers' amount of power negotiations along with offered prices. Therefore, ps t represents the weighted average of all sellers' offered prices in t th interval, as they is formulated in [START_REF] Dewatripont | Credit and efficiency in centralized and decentralized economies[END_REF].

ps t = M j=1 N i=1 x t bisj × ps t j × δs j N i=1 M j=1 x t bisj t = 1, 2, 3, ..., T (8)
Subsequently, after computing the ps t , dealers dispense these parameters to their regions' seller agents in order to let them commence with updating their next intervals' price.

ps t+1 j = ps t j -δs j × ps t j -ps t j = 1, 2, 3, ..., M ; t = 1, 2, 3, ..., T (9)
If any of the agents announce high or low price in an interval, (9) permits them to alter their prices to get close to the weighted average of the power's unit price in the next intervals.

Solution Approach

In this approach, the markets' purpose is to operate only in the benefit of buyers along with optimizing their objective function (i.e. minimizing the purchasing cost). In this case, sellers announce their prices based on their own malleability rate. The ps 1 j is denoted as j th seller's initial price, which is within the certain range declared by the dealers. Then, buyers start the purchasing procedure regarding the determined sellers' prices and parameters of the market. As a result, the objective formula with the constraints are as follows:

min f (X) = T t=1 N i=1 M j=1 x t bisj × ps t j ( 10
)
subject to:

d t bi ≤ M j=1
x t bisj × 1 -loss bisj i = 1, 2, 3, ..., N ; t = 1, 2, 3, ..., T (11)

q t sj ≥ N i=1
x t bisj j = 1, 2, 3, ..., M ; t = 1, 2, 3, ..., T (12)

ps 1 j = Randomly selected between ( p l , p u ) j = 1, 2, 3, ..., M (13)
ps t+1 j = ps t jδs j × ps t j -ps t j = 1, 2, 3, ..., M ; t = 1, 2, 3, ..., T (14)

ps t = M j=1 N i=1 x t bisj × ps t j × δs j N i=1 M j=1 x t bisj t = 1, 2, 3, ..., T (15)
∀ bi∈R B k ∀ s j ∈R S k x t bisj f low τ ι k i=1,
x t bisj , d t bi , q t sj , p l , p u , ps 1 j , ps t j , ps t , f low τ ι k ∈ Z * ; loss bisj , δs j ∈ (0, 1)

Greedy Power Matching Algorithm

Selfish trading agents have caused us to focus on finding a near optimal solution for the demand response problem in retail power markets in a greedy approach. Each of the buyers attempts to purchase all of its required power from a seller who is close to it and has announced a low price. In line with this point of view, an Interest Table related to all buyers is required prior to start power exchanging in each interval.

Interest Table

Taking into account all the constraints related to the markets and agents, an interest table is created by buyers to demonstrate their desired value in having negotiation with sellers. For instance, in this approach, each buyer's satisfaction is in purchasing the power from the sellers, who have not only been close to the buyer, but also announced low prices. As an example, Fig. 1 illustrates a city, in which there are five buyers and sellers in the third region. The initial prices are distributed haphazardly between the (1000 ± 500)$ for sellers.

where it shows the i th buyer's desired value of the j th seller, toward purchasing d t bi units of power in t th interval. Due to the power loss, it is obvious that a buyer hopes to purchase from a seller who has ability to fulfill its demand completely, with both lower price and power loss attributes. Table 1

demonstrates a sample interest table.

Considering all the interest vectors gathered from buyers, dealers combine them to form an interest table, and then commence to run the Greedy Power Matching procedure. In each time interval, a random permutation of the buyers is created. Then, each buyer attempts to create its own interest vector. After that, it starts purchasing its required demand from the sellers who are in the first element of its interest vector. After running this procedure for all the buyers, if a buyer fails to satisfy its demand and also is unable to find a seller with available surplus power in its region, then, it will buy the rest from the other sellers in the neighbored regions using the region to region purchase sub-algorithm. Similarly in this sub-algorithm, one random permutation of unsatisfied buyers is created at the first and then, each of them creates its own interest vector and search for the appropriate sellers. Finally, if the buyer's demand still is not satisfied yet, it should buy from the macro-station (i.e. region to macro-station purchase process). As a result, finding the optimal sequence of buyers, which want to minimize their objectives, makes it necessary to calculate all the permutations in order to achieve the optimal one. In this regard, the problem is NP-hard and rapidly becomes computationally intractable with growing size of the problem. Thence, evolutionary computation techniques come to help in optimizing the objective and its relevant constraints.

Evolutionary Computation

Evolutionary Algorithms (EAs) are one of the most well-known meta-heuristic search mechanisms which utilized for the optimization problems [START_REF] Bäck | An overview of evolutionary algorithms for parameter optimization[END_REF]. Evolutionary algorithms form a subset of evolutionary computation, in which they generally only involve techniques and implementing mechanisms inspired by biological evolution such as reproduction, mutation, recombination, natural selection and survival of the fittest.

In the evolutionary algorithm, firstly, we generate a random population of feasible solutions for the problem. In this literature, each solution represents the matching tables of the buyers and sellers. Then, these randomly generated solutions try to reach the optimal solution of the problem by using natural parameters as mentioned before in consecutive generations. Considering the randomly generated population in the first step, we used the "decentralized evolutionary greedy power matching algorithm", as mentioned in the previous section. Candidate solutions in the optimization problem play the role of individuals in a population and the cost function. In this process, there are two main forces that form the basis of evolutionary systems [START_REF] Črepinšek | Exploration and exploitation in evolutionary algorithms: a survey[END_REF]:

• Selection acts as a force increasing quality.

• Recombination and Mutation create the necessary diversity and thereby facilitate the solutions' novelty.

In this evolutionary algorithm, we have used a simple tournament selection, with linear crossover and exchange mutation procedures. In addition, an efficient "constrainthandling" sub-algorithm is also presented for enhancing the reliability of feasible solutions [START_REF] Deb | An efficient constraint handling method for genetic algorithms[END_REF].

Tournament Selection Tournament selection is a method of choosing a solution from a set of solutions in the evolutionary computations. It runs a tournament between P randomly chosen solutions (i.e. tournament size=P ). Then, the winner (i.e. the one with the best fitness) will be chosen for using in the crossover procedure.

Linear Crossover Linear crossover procedure gets two solutions and then combines them linearly with the probability of α, in order to produce two other solutions. These new solutions will be the ones in the offspring population. In the revised version of this procedure, we compare the fitness value of these newly generated solutions with their parents and then choose two best ones for using in the mutation procedure.

Exchange Mutation Mutation is an evolutionary operator used to preserve variety from one solution to the other one, where the solution may change entirely from the previous one. Hence, evolutionary algorithm can come to better solution by using mutation. Mutation parameters depending on the nature of the problem are different. We applied a mechanism, in which the mutation procedure exchanges amount of some negotiated power between two randomly selected buyers and sellers.

Constraint Handling Sub-Algorithm An efficient constraint-handling technique is a key element in design of competitive evolutionary algorithms to solve optimization problems [START_REF] Deb | An efficient constraint handling method for genetic algorithms[END_REF]. We proposed a greedy constraint handling sub-algorithm, in which all solutions of the offspring population will be refined in order to be assure of their feasibility. Regarding the discussing literature, refining is checking the solution in order to find any probable errors (e.g. having "un-satisfied buyers" or "over-sold sellers")in the power matchings.

Experimental Evaluation

In this section, the setting of the data used to evaluate the model considering a community of agents and the results obtained from the greedy power matching algorithm are provided.

Experimental Setup

We begin by clarifying power markets', trading agents' and evolutionary algorithm settings as follows.

Power Markets A city within a square of 10 km×10 km, in which it encompasses the macro-station which is far from the square, and K regions is simulated. A power market, which has a unique dealer is implemented in each of the regions. All of the dealers cooperate in order to decide on announcing an initial price range such as (1000 ± 500) $. Due to the problems in actual implementation, the sellers choose an initial price for themselves haphazardly. Having 24 consecutive time intervals, and also analogous to [START_REF] Machowski | Power system dynamics: stability and control[END_REF], where the surplus and required powers is different for the buyers and sellers, are concerned.

As mentioned previously, there is power loss in power transfer. This loss is calculated as follows: loss bisj = 0.01 × distance bisj i = 1, 2, 3, ..., N ; j = 1, 2, 3, ..., M (18)

loss bim = 0.3 × distance bim i = 1, 2, 3, ..., N (19)
Equation (18) exhibits power loss between i th buyer and j th seller, regarding their distance. Owing to have a region to macro-station purchase possibility, (19) is also defined as the power transfer loss between i th buyer and the macro-station.

Trading Agents N buyers and M sellers are settled randomly in K regions. Each s ∈ R S k and b ∈ R B k has a q ∈ Q and d ∈ D respectively. In addition, these parameters are supposed to be uniformly distributed among ((7, 316) MW) and ((8, 346) MW) for buyers and sellers respectively [START_REF] Machowski | Power system dynamics: stability and control[END_REF].

Evolutionary Algorithm Setting We have used tournament selection operator (tournament size=2) along with linear crossover (crossover percentage=80) and exchange mutation (mutation probability percentage=20). Moreover, the generation and population sizes are equal to 400 and 100, respectively.

Experimental Results

In order to evaluate our proposed approach and algorithms, a community of agents is considered. Hereinafter, all the results' figures are drawn out from the 25 × 25 community (Fig. 1). Running evolutionary greedy algorithm necessitates randomly generating the first population. Besides, having infinite power production by sellers, informs that this greedy approach results in an efficient and optimal power matching. Unfortunately, this assumption is not practical. Hence, finding the best sequence of buyers in buying procedure is the main challenge in power matching. Finding the optimal solution under these conditions, needs computing all the possible permutation of the buyers.

Figure 2(a) illustrates the fitness diagram obtained from running the evolutionary greedy power matching algorithm on the proposed solution approach. As pictured clearly, the algorithm outputs one solution as the best one in each generation. In the next generations, it tries to improve the initially randomly generated population by the evolutionary parameters to find the better solutions. The descending order of the Fig. 2(a) informs that the algorithm attempts to get as close as possible to the optimal permutation of the buyers. Furthermore, having eagerness to purchase the required powers from the sellers who have announced lower prices is another proof for its descending manner. Although coming to better solution in power matching problem is important, but finding the appropriate and near-optimal solution in a logical and polynomial time is also substantial. Therefore, increasing the population and generation sizes results in increasing the calculation time. As mentioned previously, based on the proposed solution approach and market assumptions, we have used the Integer Linear Programming (ILP) techniques toward solving the matching problem. Hence, due to the NP-Hardness nature of the discussing problem, it is not possible to solve or oven compare with the traditional linear programming techniques.

In order to analyze the robustness of the iterative price updating rule, in which sellers change their announced prices in each interval, we survey the obtained results based on multiple perspective. Figure 2(b) demonstrate all the sellers price changes in successive intervals. This price fluctuations is gathered from the best solution of the last generation. The sellers announced their initial price randomly. Then, in the next intervals, they altered their prices based on their both malleability rate from the market parameter and the weighted-median of other sellers offered prices. For instance, S9 and S24 have announced their initial prices close to each other. However, having difference in their malleability rate has incurred that they could not update their prices in the same order. Along with the malleability rates, the amount of negotiated power is also significant in price updating. Suppose there is a seller which sold all its produced power in a interval. Intuitively, it does not need to modify its next interval's power price rapidly if its malleability rate from the market does not very high. However, there may be a seller which could not sell as much as possible and therefore, it should change its next prices in order to increase its selling amount. Besides, there were some sellers that announced their initial price far from each other (e.g. S24 and S11). Nonetheless, they attempted to reach the price which the markets preferred. This issue also can be looked at from two perspectives. If a seller has sold all its surplus power at a specific price, probably it has announced a very low price. As a result, the market dealers forced it to change its next prices in order to prevent the market from crisis circumstances. Beside this point of view, the seller might be unable to sell its powers and therefore it has forced to decrease its next intervals' prices to be able to sell its powers. Finally, if an agent, announces an initial price approximately close to the weighted average of the power price, it is not vital to alter its next prices rapidly.

Conclusion and Future Work

In this paper, we have proposed a decentralized greedy resource allocation mechanism based on the competition, which manages the demand response problem in power markets. In this regard, a solution approach is proposed, in which electricity markets behave in the benefit of buyers. In this approach, sellers in each interval, based on the markets' available information and their relevant parameters such as malleability rate from the market, offer their own price for each unit of power. Then, buyers create their own interest vectors and start purchasing their required electricity from the sellers who are in the first element of their interest vector. In addition, in order to organize an equilibrium market, considering both of the sellers and buyers who have roles in advancing toward it, a greedy power matching algorithm is also proposed to allocate the energy produced by the sellers and the macro-station to the buyers. Finding a near-optimal power matching solution due to NP-Hardness nature of the matching problems, has motivated us to use evolutionary techniques in demand response optimization regarding the buyers objectives. As some future work, scrutinizing the possibility of having self-learning buyers in power markets along with considering on-line predictive algorithms, considering the markets in the benefit of sellers or in a comprehensive multi-objective manner can be considered.

Fig. 1 .

 1 Fig. 1. Buyers' and sellers' location

b 9 b 9 b 9 s 11 s 12 s 14 s 10 s 13 b 10 b 10 b 10 s 14 s 12 s 11 s 13 s 10 b 12 b 12 b 12 s 14 s 12 s 11 s 13 s 10

 10 Each element of the interest tables is created by:Interest t bisj = d t bi × ps t j1 + loss bisj i=1,2,3,...,N ;j=1,2,3,...,M ;t=1,2,3,...,T

Fig. 2 .

 2 Fig. 2. Fitness diagram and sellers' announced price update changes

Table 1 .

 1 Sample interest table of R3

Sellers

Buyers b 2 b 2 b 2 s 11 s 12 s 14 s 10 s 13 b 8 b 8 b 8 s 12 s 11 s 14 s 10 s 13