# A Greedy Agent-Based Resource Allocation in the Smart Electricity Markets

Armin Ghasem Azar, Mansoor Davoodi, Mohsen Afsharchi, Bahram Sadeghi Bigham

<figure><img src="image_1.png" /></figure>

## To cite this version:

Armin Ghasem Azar, Mansoor Davoodi, Mohsen Afsharchi, Bahram Sadeghi Bigham. A Greedy Agent-Based Resource Allocation in the Smart Electricity Markets. 10th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), Sep 2014, Rhodes, Greece. pp.150-161, 10.1007/978-3-662-44654-6_15. hal-01391310

HAL Id: hal-01391310

https://inria.hal.science/hal-01391310

Submitted on 3 Nov 2016

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>
# A Greedy Agent-based Resource Allocation in the Smart Electricity Markets

Armin Ghasem Azar¹, Mansoor Davoodi¹
Mohsen Afsharchi², Bahram Sadeghi Bigham¹

¹ Department of Computer Science and Information Technology
Institute for Advanced Studies in Basic Sciences, Zanjan, Iran
{a.ghasemazar, mdmonfared, b_sadeghi_b}@iasbs.ac.ir

² Department of Electrical and Computer Engineering
University of Zanjan, Zanjan, Iran
afsharchim@znu.ac.ir

**Abstract.** 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.

## 1 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 two-way streams of electricity and information to create an autonomous energy delivery network [1]. 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 [2]. 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 [3]. 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 [4], 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 [5]. 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 [6]. 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 [7].

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.

## 2 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 [5, 8]. Furthermore, many studies have been conducted in various aspects of these markets, specially in using multi agent systems and information systems [5, 9]. 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 [5].

Besides, some of the researches in the field of the energy optimization, including
those reported in [10, 11], 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 [10], 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 [11].
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.

## 3 System Model

Visualizing a city with the self-healing power grid necessitates considering the multi-
ple 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 ex-
changes 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_k^B$ and $R_k^S$ respectively. Finally, it is assumed that the system model is studied for consecutive independent intervals, $t = 1, 2, \dots, T$.

Analyzing essential parameters to obtain an optimal solution in power matching of buyers and sellers, represents the substantial challenges in demand response problem [12]. 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.

## 3.1 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 [1], 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 $\delta$ 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_{b_i s_j}^t \in \mathbb{Z}^*$ is represented as the number of power units which the $i^{th}$ buyer has purchased from the $j^{th}$ seller. $\mathbb{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 ($\tau_{lk}$) has a maximum capacity of power transferring which is denoted by $flow_{\tau_{lk}} \in \mathbb{Z}^*$. Limitation in power transfer using the distribution lines mentions that sellers cannot transfer the power more than the transmission lines’ capacity [13].

$$ \begin{array}{l} \forall \tau_{lk} \text{ such that } \displaystyle\sum_{\forall b_i \in R_k^B} \sum_{\forall s_j \in R_k^S} x_{b_i s_j}^t \le flow_{\tau_{lk}} \qquad (1) \\ i=1,2,3,\dots,N; j=1,2,3,\dots,M; t=1,2,3,\dots,T; k=1,2,3,\dots,K \end{array} $$

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 [1]. This exchange is expressed by $loss_{b_i s_j}$. 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_{b_i s_j}$. For convenience, it is assumed that only the euclidean distance between a buyer and seller has impact on the power loss.
## 3.2 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_{b_i}^t$ in interval $t$. Thereupon:

$$B = \{b_1, b_2, \dots, b_N\} \qquad (2)$$

$$D_{b_i} = \{d_{b_i}^1, d_{b_i}^2, \dots, d_{b_i}^T\} \qquad i = 1, 2, 3, \dots, N \quad (3)$$

$$d_{b_i}^t \le \sum_{j=1}^{M} (x_{b_i s_j}^t \times (1 - loss_{b_i s_j})) \qquad i = 1, 2, 3, \dots, N; t = 1, 2, 3, \dots, T \quad (4)$$

Equation (2) demonstrates the buyers set. Equation (3) shows the demand set of the $i^{th}$ buyer during all the intervals. Furthermore, $d_{b_i}^t \in \mathbb{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) [14], and aim on producing power for selling, are known as sellers. Then:

$$S = \{s_1, s_2, \dots, s_M\} \qquad (5)$$

$$Q_{s_j} = \{q_{s_j}^1, q_{s_j}^2, \dots, q_{s_j}^T\} \qquad j = 1, 2, 3, \dots, M \quad (6)$$

$$q_{s_j}^t \ge \sum_{i=1}^{N} x_{b_i s_j}^t \qquad j = 1, 2, 3, \dots, M, t = 1, 2, 3, \dots, T \quad (7)$$

Equation (5) shows the sellers set. Equation (6) demonstrates the set of surplus powers for the $j^{th}$ seller during all the intervals. Furthermore, the $q_{s_j}^t \in \mathbb{Z}^*$ is the number of the power unit that the $j^{th}$ seller has for selling in the $t^{th}$ interval. Equation (7) mentions that the sellers cannot sell more than their surplus powers in the $j^{th}$ interval.

## 3.3 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_j^t \in \mathbb{Z}^*$ demonstrates the $j^{th}$ seller's surplus power price in the $t^{th}$ interval. Consecutively, the $\delta_{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, $\overline{ps}^t$ represents the weighted average
of all sellers' offered prices in $t^{th}$ interval, as they is formulated in (8).

$$ \overline{ps^t} = \frac{\sum_{j=1}^{M} \left( \left( \sum_{i=1}^{N} x_{b_i s_j}^t \right) \times ps_j^t \times \delta_{s_j} \right)}{\sum_{i=1}^{N} \sum_{j=1}^{M} x_{b_i s_j}^t} \quad t = 1, 2, 3, \dots, T \quad (8) $$

Subsequently, after computing the $\overline{ps}^t$, dealers dispense these parameters to their regions' seller agents in order to let them commence with updating their next intervals' price.

$$ ps_j^{t+1} = ps_j^t - (\delta_{s_j} \times (ps_j^t - \overline{ps}^t)) \quad j = 1, 2, 3, \dots, M; t = 1, 2, 3, \dots, T \quad (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.

## 3.4 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_j^1$ 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) = \sum_{t=1}^{T} \sum_{i=1}^{N} \sum_{j=1}^{M} x_{b_i s_j}^{t} \times ps_{j}^{t} \quad (10) $$

subject to:

$$ d_{b_i}^t \le \sum_{j=1}^{M} (x_{b_i s_j}^t \times (1 - loss_{b_i s_j})) \quad i = 1, 2, 3, \dots, N; t = 1, 2, 3, \dots, T \quad (11) $$

$$ q_{s_j}^t \ge \sum_{i=1}^{N} x_{b_i s_j}^t \quad j = 1, 2, 3, \dots, M; t = 1, 2, 3, \dots, T \quad (12) $$

$$ ps_j^1 = \text{Randomly selected between } (p_l, p_u) \quad j = 1, 2, 3, \dots, M \quad (13) $$

$$ ps_j^{t+1} = ps_j^t - (\delta_{s_j} \times (ps_j^t - \overline{ps}^t)) \quad j = 1, 2, 3, \dots, M; t = 1, 2, 3, \dots, T \quad (14) $$

$$ \overline{ps}^t = \frac{\sum_{j=1}^{M} \left( \left( \sum_{i=1}^{N} x_{b_i s_j}^t \right) \times ps_j^t \times \delta_{s_j} \right)}{\sum_{i=1}^{N} \sum_{j=1}^{M} x_{b_i s_j}^t} \quad t = 1, 2, 3, \dots, T \quad (15) $$

$$ \sum_{\forall b_i \in R_k^B} \sum_{\forall s_j \in R_k^S} x_{b_i s_j}^t \le flow_{\tau_{l_k}} \quad i=1,2,3,\dots,N; j=1,2,3,\dots,M; t=1,2,3,\dots,T; k=1,2,3,\dots,K \quad (16) $$

$$ x_{b_i s_j}^t, d_{b_i}^t, q_{s_j}^t, p_l, p_u, ps_j^1, ps_j^t, \overline{ps}^t, flow_{\tau_{l_k}} \in \mathbb{Z}^*; loss_{b_i s_j}, \delta_{s_j} \in (0, 1) $$
## 4 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.

<figure><img src="image_3.png" /><figcaption>Fig. 1. Buyers' and sellers' location</figcaption></figure>

<table><caption>Table 1. Sample interest table of R3</caption><thead><tr><th rowspan="2"></th><th rowspan="2"></th><th colspan="5">Sellers</th></tr><tr><th>s11</th><th>s12</th><th>s14</th><th>s10</th><th>s13</th></tr></thead><tbody><tr><th rowspan="5">Buyers</th><th>b<sub>2</sub></th><td>s11</td><td>s12</td><td>s14</td><td>s10</td><td>s13</td></tr><tr><th>b<sub>8</sub></th><td>s12</td><td>s11</td><td>s14</td><td>s10</td><td>s13</td></tr><tr><th>b<sub>9</sub></th><td>s11</td><td>s12</td><td>s14</td><td>s10</td><td>s13</td></tr><tr><th>b<sub>10</sub></th><td>s14</td><td>s12</td><td>s11</td><td>s13</td><td>s10</td></tr><tr><th>b<sub>12</sub></th><td>s14</td><td>s12</td><td>s11</td><td>s13</td><td>s10</td></tr></tbody></table>

Each element of the interest tables is created by:

$$Interest_{b_i s_j}^t = \frac{d_{b_i}^t \times ps_j^t}{1 + loss_{b_i s_j}} \quad (17)$$

where it shows the $i^{th}$ buyer's desired value of the $j^{th}$ seller, toward purchasing $d_{b_i}^t$ 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 neighboring 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.

**4.1 Evolutionary Computation**

Evolutionary Algorithms (EAs) are one of the most well-known meta-heuristic search
mechanisms which utilized for the optimization problems [7]. Evolutionary algorithms
form a subset of evolutionary computation, in which they generally only involve tech-
niques and implementing mechanisms inspired by biological evolution such as repro-
duction, 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 [15]:

* **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 “constraint-
handling” sub-algorithm is also presented for enhancing the reliability of feasible solu-
tions [16].

**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 $\alpha$, 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 [16]. 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.

# 5 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.

## 5.1 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 co-operate 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 [13], 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_{b_i s_j} = 0.01 \times distance_{b_i s_j} \qquad i = 1, 2, 3, ..., N; j = 1, 2, 3, ..., M \quad (18)$$

$$loss_{b_i m} = 0.3 \times distance_{b_i m} \qquad i = 1, 2, 3, ..., N \quad (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 \in \mathbb{R}_k^S$ and $b \in \mathbb{R}_k^B$ has a $q \in Q$ and $d \in 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 [13].

**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.

## 5.2 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 even 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
<figure><img src="image_4.png" /><figcaption>Fig. 2. Fitness diagram and sellers’ announced price update changes</figcaption></figure>

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 an 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.

# 6 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.

## References

1. Fang, X., Misra, S., Xue, G., Yang, D.: Smart grid: new and improved power grid: a survey. Communications Surveys & Tutorials, IEEE 14(4) (2012) 944–980

2. Rogers, A., Ramchurn, S.D., Jennings, N.R.: Delivering the smart grid: Challenges for autonomous agents and multi-agent systems research. In: AAAI. (2012)

3. Albadi, M., El-Saadany, E.: Demand response in electricity markets: An overview. In: IEEE Power Engineering Society General Meeting. Volume 2007. (2007) 1–5

4. Papavasiliou, A., Hindi, H., Greene, D.: Market-based control mechanisms for electric power demand response. In: Decision and Control (CDC), 2010 49th IEEE Conference on, IEEE (2010) 1891–1898

5. Bichler, M., Gupta, A., Ketter, W.: Research commentary-designing smart markets. Information Systems Research 21(4) (2010) 688–699

6. Lawler, E.L.: The quadratic assignment problem. Management science 9(4) (1963) 586–599

7. Bäck, T., Schwefel, H.P.: An overview of evolutionary algorithms for parameter optimization. Evolutionary computation 1(1) (1993) 1–23

8. Dewatripont, M., Maskin, E.: Credit and efficiency in centralized and decentralized economies. The Review of Economic Studies 62(4) (1995) 541–555

9. Lamparter, S., Becher, S., Fischer, J.G.: An agent-based market platform for smart grids. In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: Industry track, International Foundation for Autonomous Agents and Multiagent Systems (2010) 1689–1696

10. HomChaudhuri, B., Kumar, M.: Market based allocation of power in smart grid. In: American Control Conference (ACC), 2011, IEEE (2011) 3251–3256

11. HomChaudhuri, B., Kumar, M., Devabhaktuni, V.: A market based distributed optimization for power allocation in smart grid. In: ASME 2011 Dynamic Systems and Control Conference and Bath/ASME Symposium on Fluid Power and Motion Control, American Society of Mechanical Engineers (2011) 735–742

12. Kirschen, D.S.: Demand-side view of electricity markets. Power Systems, IEEE Transactions on 18(2) (2003) 520–527

13. Machowski, J., Bialek, J., Bumby, J.: Power system dynamics: stability and control. John Wiley & Sons (2011)

14. Lasseter, R.H.: Microgrids. Power Engineering Society Winter Meeting, 2002. IEEE 1 (2002) 305–308

15. Črepinšek, M., Liu, S.H., Mernik, M.: Exploration and exploitation in evolutionary algorithms: a survey. ACM Computing Surveys (CSUR) 45(3) (2013) 35

16. Deb, K.: An efficient constraint handling method for genetic algorithms. Computer methods in applied mechanics and engineering 186(2) (2000) 311–338