1. Introduction

Timely and complete informing about upcoming events or important potential global threats is one of the population security management tasks in the modern information world. Especially this problem is topical for highly populated megalopolises and in the same time for megalopolises with high concentration of information received by everyone ^[1].

Channels of the rapid response (radio, TV, internet, cellular and paging) are necessary for the timely warning of emergency situations, potential danger factors, natural or technogenic emergencies, but for permanent or advance information it is better to use the outdoor advertising and street actions for the direct contact ^[2]. The outdoor advertising on billboards (outdoor advertising media with or without backlight, on which permanent or removable advertisements are placed) is being used for the social advertising because its cheapness ^[3].

Typically, municipal and state programs, such as accident prevention, life safety, prevention of epidemics of deadly diseases or their prophylaxis, as well as information programs to attract attention to the problems of persons with disabilities, children left without parental care, homeless animals, and others have rigid and sometimes extremely limited budget ^[4].

At the same time, advertising structures and carriers tend to belong to private companies that provide their rent on a commercial basis. We overlook aspect of the interaction local executive authorities and commercial organizations at the level of legal relations. For example, there are no preferences provided for social advertising at the state level in Ukraine ^{[4, 5]}. In what follows we consider that the municipality of a city, region, state or central government drawn for social advertising as a subject of market relations.

In this article we consider the problem of optimizing the placement of advertising on outdoor social carriers in the conditions of limited advertising budget. Similar problems for placing advertising units on the Internet solved earlier ^{[6, 7]} as a linear programming problem with constraints. In ^[6] the classical formulation and solution of the problem is given using the accurate method of linear programming. At the same time authors in ^[7] propose to solve the problem with the restrictions (so-called traveling salesman problem) using a heuristic method involves finding a random solution for the limited time.

Researchers, which considered the problem earlier, did not consider the intersection of audience billboards with the same content. To maximize the audience reach billboards should be placed as far as possible from each other within the administrative unit. The proposed approach in this paper will consider the peculiarities of the mutual arrangement of billboards which is capable to increase the effectiveness of advertising contacts either to reduce it. This feature allows you to position the solving problem as a special case of an independent set of vertices covering ^[8].

2. Problem of Optimization the Advertising Budget and Methods of Artificial Immune System Modeling

The main indicator of advertising efficiency is the number of contacts with the audience for a certain period of time ^[9]. The number of views of the advertising message per day is accepted as contacts. This indicator is random, it is depending on a day of week, time of year, weather, etc., and it can be characterized by the magnitude of estimate mathematical expectation and also the possible range of variation.

Since we are talking about advertising on commercial terms we consider the magnitude of costs of an advertising campaign as the second characteristic, which we should take into account while choosing media advertising. The latter consists of the cost of manufacturing, placing advertising products (components, in general nonlinearly depending on the amount) and the rental cost of the media per unit of time ^[10]. For convenience costs per unit of time can also be adjusted to a period of one day. The cost of renting the media depends on its location, the availability of the illumination, visibility, value of the land on which the media is located, time of year and other commercial factors. In the future, we assume that the cost of the lease is fixed at the time of solving the problem and will remain unchanged for the advertising campaign ^[9].

The task of choosing an optimal subset media (billboards), which would provide the greatest possible efficiency of commercial advertising for a given maximum level of costs considered in detail in ^[11].

Objective function for the optimization problem is

(1)

- the vector of variables consisting of binary elements which correspond affordable advertising media, can take the value "0" - the billboard is not used, or "1" - billboard is used, ; - evaluation of the mathematical expectation of the number of contacts with the audience for media per day, .

Constraints in the problem are as follows:

(2)

(3)

(4)

where and - unnecessary restrictions on the number media that can be caused by conditions of conducting an advertising campaign, unless otherwise noted, and are accepted; - the cost of manufacturing units and placement of printed materials; - the cost of renting the media per day, ; - advertising budget.

The latter limitation (4) causes the binary space of searching solutions. Thus the problem (1) - (4) belongs to the class of binary combinatorial constrained optimization problems. It is a direct analogue of the famous knapsack problem ^[12].

Authors ^{[11, 12]} shown that the problem (1) - (4) is NP-hard, that is why exact methods for its solution, namely, the method of exhaustive search and dynamic programming techniques are effective only for small dimensions ().

If each of the advertising media can be used a different number of days, but the owners of the advertising areas provide rebates for the duration of use of squares and the number of leased media at the same time, the complexity of the problem rises by several orders of magnitude, and its solution is directly becomes impossible even for ^[11].

To solve such problems authors ^[13] propose to use a genetic algorithm (GA), for which a binary space is natural. However, the use of GA in a constrained optimization problem imposes the need to take in account constraint violations in the objective function.

The constraint (4) is eliminated by the nature of the genetic algorithm, but for (2) and (3) it is necessary to use a specific penalty function. Thus, the GA for problem (1) takes the form

(5)

(6)

(7)

where - the weight penalty for violation of restrictions on the cost of advertising campaign, it is proposed to use - average response per unit of invested funds; - weight penalty for violation of restrictions on the amount of areas used, it is proposed to use .

Problem (5) - (8) has an absolute form, in which solutions that go beyond the range of permissible values caused (2) - (3) cause stiff penalties. Thus, any of the solutions outside the tolerance range is always worse than the permissible value.

Method, which is based on artificial immune system modeling, is proposed to be used for the solving this problem as an alternative to the classic genetic algorithm. Artificial immune system (AIS) is an information technology that uses concepts machine and some of the achievements of theoretical immunology for applications ^[14]. A large number of different methods for the numerical solution of applied problems of data analysis, pattern recognition, computer security, fault diagnosis of technical objects, optimization, etc. are based on AIS.

Methods of AIS are aimed at solving global optimization problems, inspired by some aspects of the behavior of the human immune system in protecting the body from its external factors (pathogens and antigens).

Protective cells of the immune system (antibodies) undergo many changes, which aim to create cells that provide the best protection against this factor. The result is a large number of different antibodies and those who are the best fitted for protection win in a combating with pathogen. The human immune system retains its "memory" of winning the antibodies on the basis of which the same antibodies are produced by repeated penetration into the body similar pathogen.

The immune algorithm (IA) offered here imitate properties of natural immune system and it is based on principles of the somatic theory ^[15] and a network hypothesis ^[16].

Somatic theory states that increasing of the diversity of antibodies is due to somatic recombination and mutation of genes. The assumption that control of breeding clones occurs because of mutual recognition of antibodies that function as network is justified within the network hypothesis ^{[15, 17, 18, 19]}. In the course of evolution, the immune system of the highest mammals had gain ability to destroy antigens by antibodies (Figure 1).

Figure 1. Mechanism of formation of antibodies in the immune system

Download as

PowerPoint Slide

Larger image(png format)

Figures index

Veiw figure

View current figure in a new window

View next figure

According to the somatic theory, the genetic information contained in numerous segments of the genes arrange in a chromosome. In the development of lymphocytes original in a marrow, these segments combined because of genetic recombination and formed genes of the immunoglobulin’s in B-lymphocytes in an awake state. Somatic mutations during the immune reactions occur with high frequency, creating additional variability of the gene. As it had been shown by researchers, in natural immune system these two processes provide a necessary variety of antibodies and a regulation of a breeding of clones ^[15].

On Figure 1 work of immune system from the point of view of processes of handling and control of the information is shown. Using this schema it is possible to present informational processes in immune system in the form of algorithm which is put in the following sequence of the formalize steps:

Step 1. Discernment of an antigen. The immune system distinguished antigenic encroachment and defined, whether it are connected with foreign or with characteristic cell of an organism. This process corresponded to an establishment of an aspect of a problem of optimization.

Step 2. Generating of antibodies by memory cells. Memory cells were activate and made antibodies for an erasure of the yield antigen. It corresponded to a mention of a successful solution of a similar problem (let, and for other antigen) in the past.

Step 3. Evaluation of affinity. Based on a biochemical discernment of superficial structure of a new antigen there are a selection of the cells that produce most suitable antibodies. Based on magnitude of affinity antibodies, which are the most appropriate for antigen, are selected, which is equivalent to finding the optimal solution.

Step 4. Differentiation of lymphocytes. If concentration of antibodies exceeded define border of concentration in advance then some B-lymphocytes, antibodies of which are corresponded to an antigen, become memory cells or suppressor cells. It can be interpret as conservation of the conforming solution for the following step of searching. Suppressors are necessary for excision of excess of candidates in reproduction in new generation.

Step 5. Inducing and suppression of antibodies. Antibodies are cloned and mutated depending on affinity. If the antibody has a higher affinity to an antigen, it proliferates more actively, but the multiplication of antibody concentration is too high, is suppressed. Along with tracing of local maximums, it corresponds to maintaining the diversity of search directions.

Step 6. Breeding of antibodies. For response to antigens that have not seen before and did not resemble any of the known solutions the formation of new lymphocytes instead of antibodies which were removed in the previous step is produced in the bone marrow.

In the nature the described process is continuous - antibodies produced by an organism both for met antigens, and also for its possible variants (mutations). In the computer simulation process of algorithm it can be stopped after a set time or after a fixed amount of generations during which fitness of antibodies does not increase.

To avoid misunderstanding, we introduce notations and give definition of the several special terms borrowed from biology which are taken in the following sense:

- A cell (antibody) - a solution of a problem;

- Affinity - the magnitude designate usefulness of a cell which is calculated as magnitude of target function relatively to entire population;

- Population - set of the cells that participate in process of optimization at the current stage;

- A clone - a cell formed from another by its duplication;

- A mutation - a random modification of the vector components by a certain law.

Further in formulas and algorithms the following notations are applied:

- cell;

- the value of target function corresponding to a cell;

- population of cells with given energy;

- components of the cell that exist in the measuring space (coordinates);

- affinity (usefulness) of the cell relative to the current population;

- population of memory cells (are not part of population );

- Set of the cell's clones (descendants) produced on the current iteration of a method;

- set of clones (descendants) of all cells produced on the current iteration of a method;

– clone (descendant) of cell;

- the best (which corresponds to the highest affinity) clone of cell in a generation;

- An amount of clones generated from each cell population.

Thus, the method of artificial immune system modeling irrespective of its realization provides working with population of cells, each of which is a vector in the space of independent variables. In our case the vector consist of the binary variables which correspond to advertising media.

The basic operators whom the method of modeling of synthetic immune system used were operators of cloning, mutations, clonal selection and compression of population.

The cloning is a creation of the set of replicas for each of cells of current generation

(8)

In turn, the mutation is a modification of a cell in a random way. For a binary vector the mutation is realized by the formula

(9)

Amount of bits that are subjects of mutation on each step are determined by the intensity, which depends on the affinity (outlined below).

The operator of clonal selection provides substitution of current population by the best of descendants that had passed cloning and mutation

(10)

Population contraction operator removes redundancy of population, except the worst one from the close solutions which satisfy the requirement

(11)

where - a fixed threshold of proximity (determined by the dimensionality of space and features of the implementation of the algorithm); - the symbol of a norm, depending on the metric of space could be calculated in one way or another (for binary space the Manhattan metric is used).

A plurality of memory contained the fixed amount of the various best solutions found during the operating time of algorithm. Cells from memory are used as duty during the formation of the new generation.

Cloning and mutation operators provide a random local search in the vicinity of each of the cells like genetic algorithm which is discussed earlier. Contraction operator population allowed accelerating ascension of a method and reduction of computing costs. Application of memory cells prevents you from losing the global optimum region during random search.

Historically the first realization of idea of modeling of synthetic immune systems were offer in ^[20] idea to use the mechanism of immune selection for a pattern recognition. Later same idea been used and for solving optimization problems. More full analysis of the theory of basic method which was named CLONALG, is shown in ^[21].

The algorithm of CLONALG using the all basic principles of modeling method of synthetic immune systems: presence of memory cells, selection and cloning of most useful antibodies, a mutation, elimination the least useful antibodies, choice of clones proportionally to their usefulness and secure the safety of the best solutions.

The algorithm of CLONALG includes the following steps:

Step 0. Population generate from cells which components satisfy demands of restrictions of coordinates (2).

Step 1. Determined usefulness of each of antibodies of multiplicity as relative magnitude of the population for the target function.

Step 2. In multiplicity left some number of antibodies with the greatest usefulness, remaining antibodies are discarded.

Step 3. Antibodies from perspective multiplicity with capacity are cloned proportionally to their usefulness (the best cell have the most clones - , the bad - only one). All received clones form multiplicity .

Step 4. The multiplicity clones are exposed to a mutation, which intensity decrease with increase of usefulness on the formula

(12)

Where - the positive parameter of algorithm, ensure the acceptable level of a mutation.

Step 5. Determine usefulness of all clones of the multiplicity which passed a mutation, based on this discover a cell with the highest affinity. If usefulness of the given cell are higher, than any of memory cells, we changed the last with the specified clone.

Step 6. Carried out the replace of an active part of antibodies from multiplicity by new cells from multiplicity on (10). Remaining cells, we filled with new casual solutions .

Step 7. If the condition of a stop was made, a conclusion of a memory state and population, if not – return to step 1. The operating time of algorithm, an amount of cycles of cloning mutation, an amount of reversions to target function or reaching by value of affinity of some set level could be a condition of a stop.

The algorithm of CLONALG has a number of settings that essentially effect on his work. First of all, algorithm extremely depended on a choice of parameters that , the choice of which in turn depends on the type of the objective function and space dimensionality problem. In numerous launches at different dimension of the problem , were obtained empirical following settings: ; .

3. Results of the Problem Solution

In solving the problem was investigated, which consists in comparing the solutions of the problem, obtained by the genetic algorithm and artificial immune system algorithm.

As indicators of the quality of algorithms were chosen following indicators:

- best for several launches solution found by the algorithm for a set time (the number of advertising contacts);

- average over multiple runs, the solution found by the algorithm (the number of advertising contacts);

- average time to find solutions, while solutions are improving, sec;

- the average number of calls to the objective function for the time of the decision (to stop the algorithm).

Comparative results for 10 restarts a genetic algorithm (GA) and immune algorithm (IA) with various task and admissible dimension volumes of funding are shown in Table 1-Table 4 and in Figure 2, Figure 3.

Quality solutions for the first two criteria further compared with a known optimal value according to (5).

Table 1. Comparison of the accuracy of solutions using different heuristics

Download as

PowerPoint Slide

Larger image(png format)

Tables index

Veiw figure

View current table in a new window

View next table

In Table 1, we can notice a trend: while significantly increasing problem dimension genetic algorithm (GA) can't find within the time limit of the exact solution . At the same time, the algorithm implements the method of simulation of artificial immune systems (IA) at least once of 10 finds an exact solution even if the dimension of the problem 1000 considered advertising media.

Blank cells in the table correspond to insignificant (non-optimal) solutions. At $10 000 the optimal value meet 8…10 billboards; at $100 000 is at 26…31 billboards, and at $1 000 000 - at 176…214 media used (higher values correspond to larger amount ). Consideration does not make sense.

Similar results are reflected in the following tables.

Table 2. Comparison of the accuracy of solutions using different heuristics

Download as

PowerPoint Slide

Larger image(png format)

Tables index

Veiw figure

View current table in a new window

View previous table

View next table

In Table 2, the above-mentioned tendency to fall reliability and quality of the solutions proposed GA is particularly noticeable. Obtained with the help IA solutions are an important feature of repeatability - the average accuracy close to the best on multistart.

Present data from Table 1 and Table 2 in a graphic form.

Data in Figure 2 give rise to the following conclusion: as for small-scale advertising campaign financing, and at very considerable convergence of GA has a random, showing the average solution by 20-30% worse than the optimal. Even 10 restarts do not guarantee an optimal solution. GA shows the best results with an average level of funding that when you need to select several dozen carriers. However, in this algorithm still returns a random decision in the allotted time search.

Figure 2. Comparing the relative accuracy of the methods with different value of budget of the advertising campaign V: a) V = $ 10 000; b) V = $ 100 000; c) V= $ 1 000 000

Download as

PowerPoint Slide

Larger image(png format)

Figures index

Veiw figure

View current figure in a new window

View previous figure

View next figure

The following Table 3 shows a comparison of GA and IA methods time work in the same conditions. Note that the time limit of 600 seconds has been identified. Within each implementation of the algorithm was also a provision for early stopping in finding the optimal solution (it was known in advance), as well as improvements in the absence of solutions for a certain period (60 seconds).

Table 3. Comparison of time for obtaining solutions using different heuristics

Download as

PowerPoint Slide

Larger image(png format)

Tables index

Veiw figure

View current table in a new window

View previous table

View next table

As you can see, the work is more stable GA at the same dimension of the problem than the time of IA. This is primarily associated with machine cost to generate a large number of random numbers used in the mutation and crossover operators as well as to the calculation of a large number of solutions that do not improve the objective function.

What part of the time in the algorithm takes payment directly target functions, illustrated in Table 4.

Table 4. Comparison of heuristics in the number of calls to the objective function

Download as

PowerPoint Slide

Larger image(png format)

Tables index

Veiw figure

View current table in a new window

View previous table

Analysis of the results in Table 4 shows the main reason for the loss GA in comparison with IA at high dimensionality of the problem: a genetic algorithm simply does not have time to perform the same number of iterations. Since long binary vectors much time is spent on operations crossover and mutation, bearing the individual probabilistic nature of direct appeals to the target function used to order less.

This is clearly illustrated by graphs of dependency calculation time and number of calls to the objective function shown in Figure 3.

If IA fold increase in the space dimension (in this case - the number of billboards) leads to a proportional increase in time and find a solution that is characteristic of a proportional increase in calls to the objective function (line graphs).

Figure 3. Comparing the running time and function calls of the methods

Download as

PowerPoint Slide

Larger image(png format)

Figures index

Veiw figure

View current figure in a new window

View previous figure

At the same time an increase in funding (the number of potential solutions) significantly increases the duration of the program, but not significantly - the number of calls to the objective function. This is easily explained by the fact that with increasing length of the vector is more time to generate new random solutions in the process of mutation clones.

GA is also true for fold increase in proportion to the operating time dimension. At the same time the amount of funds allocated this time depends weakly, but the number of calls to the objective function does not depend at all (a drop in large dimensions due to the cutoff of 600 seconds, beyond which the algorithm halts regardless of the outcome).

From the graphs in Figure 3 is also easy to see that GA shows better work with small dimensions of the problem, when the influence of the operator crossing. In contrast, when a large dimension of the problem, when the core is the mutation operator, IA has a distinct advantage due to an order of magnitude more points of views in the search area. Given that iteration IA occur much faster, with significant (200 and more) dimensions of the problem, you should prefer IA.

4. Conclusions and Recommendations

In this paper we consider the problem of selecting a carrier of the plurality of outdoor advertising offers available in the formulation of the knapsack problem, namely, when restricted to the amount of funding.

Since the problem is NP-hard, the solution for time management is only possible heuristics. The paper proposes a variant of the heuristic based on the modeling method of artificial immune system of the human body. The basis algorithm immune operators comprise cloning, mutation, selective compression of the memory and repeating the natural processes in lymphocytes.

The proposed implementation of the algorithm was tested in the test set with known global optima for different numbers of potential solutions. Also were compared with the proposed algorithm IA known genetic algorithm GA, used previously for solving such problems.

The study showed that:

- With a substantial increase in the size of the problem GA can’t find with the allotted time of the exact solution, while the IA at least once from 10 starts find the exact solution even if the dimension of the problem in 1000 ;

- Spread the best solutions from medium- small multistart each of the algorithms that says more about the quality of the test case;

- With a small dimension of the problem GA uses fewer iterations to find a solution and find it stable, but as the dimension of 200 quality and speed of GA are much inferior than IA;

- Working time more stable GA at the same dimension of the problem than the time of IA;

- For the same amount of time IA refers to the objective function to order more, what allows to explore the search space region;

- At high dimensionality of the problem IA has a distinct advantage in speed and accuracy of the task.

As development outlined in this article, the actual introduction of the ideas seen in the objective function concepts discounts from owners of advertising space for the amount of occupied space at the same time and for the duration of the lease.

Extension of the problem can be a division of advertising messages on various media types: city lights, backlights, LED screens, etc., taking into account the characteristics of their work and the perception of the target audience.

The proposed method in this paper can also be used in the management of advertising campaigns, limited in time or finances, in modern media, including social, banner and news networks.

The proposed simulation method of artificial immune systems can be used to solve a wide range of combinatorial search and constrained optimization problems.

References

[1]	Paul, C. L., Redman, S., and Sanson-Fisher, R. W. (2003). Print material content and design: Is it relevant to effectiveness? Health Education Research: Theory and practice, ch. 18, pp. 181-190.
	In article
[2]	Andriyashkin C. Comparative analysis of Russian and foreign experience of social advertising – Available: https://www.socreklama.ru/sr_article.php?arti_id=81.
	In article
[3]	Atkin, C. and Schiller, L. (2002). The impact of public service advertising. In L. Schiller & T. Hoff (Eds.), Shouting to be heard: Public service advertising in a new media age (pp. 21-30). Retrieved February 19, 2003, Available: https://www.kaisernetwork.org/health_cast/uploaded_files/BackgroundPapers.KaiserPSAs.pdf.pdf.
	In article
[4]	Golota I. (2007) Issues of state regulation of social advertising. – Available: https://fppr.org.ua/netgorod/SSR.htm.
	In article
[5]	Law of Ukraine from 03.07.1996, № 270/967VR “About Advertising”.
	In article
[6]	Feige U., Immorlica N., Mirrokni V. and Hamid Nazerzadeh (2008) A combinatorial allocation mechanism with penalties for banner advertising. In Proceedings of the 17th international conference on World Wide Web, WWW ’08, pages 169-178.
	In article
[7]	Zhou Y., Chakrabarty D. and Lukose R. (2008) Budget constrained bidding in keyword auctions and online knapsack problems. Internet and Network Economics, volume 5385 of Lecture Notes in Computer Science, pages 566-576.
	In article
[8]	Dasgupta S., Papadimitriou C. H. and Vazirani U. (2006) Algorithms. McGraw-Hill Science/Engineering/Math. pp. 336.
	In article
[9]	Davis, Joel J. (2012) Advertising Research: Theory and Practice: Second Edition –San Diego State University.
	In article
[10]	Çetin, E., Esen, S.T. (2006) A weapon–target assignment approach to media allocation. Applied Mathematics and Computation, Volume 175, Issue 2, Pages 1266-1275.
	In article		CrossRef
[11]	Shtovba, S.D., Yakovenko, A.A. and Shtovba, O.V. (2011) Genetic optimization of outdoor advertising brands. Vestnik of Vinnytsia National Technical University. Vol 2. pp. 134-138.
	In article
[12]	Martello S. (1990) Knapsack Problems: Algorithms and Computer Implementations / Silvano Martello, Paolo Toth. John Wiley & Sons, 296 p.
	In article
[13]	Haupt, R.L., Haupt, S.E. (2004) Practical Genetic Algorithms. New Jersey: John Wiley & Sons, 253 p.
	In article
[14]	Tarakanov A. and Dasgupta, D. (2000) A formal model of an artificial immune system. Biosystems, Volume 55, Issues 1–3, Pages 151-158.
	In article
[15]	Lucinska M., Wierzchon S.T. (2009) Hybrid Immune Algorithm for Multimodal Function Optimization // Recent Advances in Intelligent Information Systems, pp. 301-313.
	In article
[16]	Rowan T.H. (1990) Functional Stability Analysis of Numerical Algorithms, Ph.D. Thesis, Department of Computer Sciences, University of Texas at Austin. Available: https://reference.kfupm.edu.sa/content/f/u/functional_stability_analysis_of_numeric_1308737.pdf.
	In article
[17]	Molga M., Smutnicki C. (2005) Test functions for optimization needs. Available: https://www.zsd.ict.pwr.wroc.pl/files/docs/functions.pdf.
	In article
[18]	De Castro, L.N., Timmis, J. (2002) An Artificial Immune Network for Multimodal Function Optimization. Proceedings of IEEE Congress on Evolutionary Computation (CEC'02). Hawaii, vol. 1, pp. 699-674.
	In article
[19]	Yildiz A.R. (2009) A novel hybrid immune algorithm for global optimization in design and manufacturing. Robotics and Computer-Integrated Manufacturing, vol. 25, pp. 261-270.
	In article		CrossRef
[20]	De Castro, L.N., Von Zuben, F.J. (2002) Learning and Optimization Using the Clonal Selection Principle. IEEE Transactions on Evolutionary Computation, vol. 6, No. 3, pp. 231-259.
	In article		CrossRef
[21]	Brownlee, J. (2007) Clonal Selection Algorithms / Technical Report 070209A, Complex Intelligent Systems Laboratory (CIS), Centre for Information Technology Research (CITR), Faculty of Information and Communication Technologies (ICT), Swinburne University of Technology. Available: https://pdf.aminer.org/000/315/118/how_to_escape_traps_using_clonal_selection_algorithms.pdf.
	In article